[Storico] Macchina di turing

[Neptune]

Inziamo subito con il dire che è più una curiosità "storica" che una domanda tecnica, a parte che non ditemi che è tecnico perchè non ci sono sezioni apposite per parlare della macchina di turing

Detto questo in delle dispense ho trovato scritto la seguente riga:

"L'unità di misura fa riferimento alla macchina di Turing, ovvero alla grandezza della porzione di nastro contenete i dati in ingresso".

Ora la curiosità che mi è sorta è questa: ma se si prende come unità di misura la porzione di nastro contenente i dati in ingresso, questo significa che questa benedetta porzione di nastro aveva una grandezza fissa e prestabilità? O non ci ho capito un razzo di quel che c'è scritto?

[Nuvolari2]

Penso fosse un'Alfa Romeo...

[Ma, te, oh.]

io studio lingue quindi prendilo con le molle, mi pare che il nastro fosse diviso parti uguali che venivano lette l'una dopo l'altra.
comunque è una macchina astratta, mi pare che non sia mai stata veramente creata.

[Alhazred]

Originariamente inviato da Ma, te, oh.
...
comunque è una macchina astratta, mi pare che non sia mai stata veramente creata.

Come no? Ma scherzi? E tutte le station wagon BMW che sono?

[Arcane]

Originariamente inviato da Neptune
O non ci ho capito un razzo di quel che c'è scritto?

This

[Alhazred]

Originariamente inviato da Neptune
...
Detto questo in delle dispense ho trovato scritto la seguente riga:

"L'unità di misura fa riferimento alla macchina di Turing, ovvero alla grandezza della porzione di nastro contenete i dati in ingresso".
...

Così è incompleto, bisognerebbe sapere anche cosa c'è scritto attorno, ad esempio: l'unità di misura di che cosa?

[Alex'87]

Originariamente inviato da Ma, te, oh.
comunque è una macchina astratta, mi pare che non sia mai stata veramente creata.

Ah sì?

[Neptune]

Originariamente inviato da Alhazred
Così è incompleto, bisognerebbe sapere anche cosa c'è scritto attorno, ad esempio: l'unità di misura di che cosa?

Si parla di complessità computazionale in tempo e dice che l'unità di misura è quella li.

Forse se dite che il nastro era suddiviso in celle intende dire che l'unità di misura presa in considerazione "è la grandezza di una cella" che forse all'epoca era come dire adesso che utilizziamo "un byte" come unità di misura e se memorizziamo un intero ne usiamo chessò 2 byte.

Dite che potrebbe filare così il discorso?

Probabilmente se la complessità in spazio se la fossero inventata più di recente avrebbero usato il byte come unità di misura ed ora non starei qui a rompere gli zebedei?

[Alhazred]

Secondo me vuol dire "dimensione dell'input" come la si intende comunemente.
Ad esempio, l'algoritmo selection sort ha complessità O(n^2) dove n è la "dimensione dell'input", ovvero la quantità di numeri (o altro) che si danno in pasto all'algoritmo affinché li ordini.

Riferito alla macchina di Turing si tratta della porzione di nastro che contiene tutto l'input da processare, ma dipende appunto dall'input, non sono... che so... sempre 5cm.

[Neptune]

Originariamente inviato da Alhazred
Secondo me vuol dire "dimensione dell'input" come la si intende comunemente.
Ad esempio, l'algoritmo selection sort ha complessità O(n^2) dove n è la "dimensione dell'input", ovvero la quantità di numeri (o altro) che si danno in pasto all'algoritmo affinché li ordini.

Riferito alla macchina di Turing si tratta della porzione di nastro che contiene tutto l'input da processare, ma dipende appunto dall'input, non sono... che so... sempre 5cm.

La complessità che intendi tu credo che sia la complessità in tempo e viene calcolata per un "n" che tende a più infinito. Anche se anche qui effettivmente per quanto grando può essere "n" deve comunque avere un unità di misura.

Per la complessità in tempo si conta se ci sono array allora è n*grandezza del tipo dell'array e cose cosi. E ad ogni modo serve un qualche tipo di unità di misura.

Però appunto non riesco a capire che senso ha fare un riferimento alla macchina di turing.

Conta che nella pagine successive delle slide da un modello di costo in cui dice che ogni variabile di tipo elementare ha costo unitario, gli array invece hanno un costo pari ad n*costo del singolo elemento (quindi se è un array di interi è n*1). Il punto è che il costo è unitario, ma qual'è l'unita di misura? che centra la macchina di turing? mbho!