Cos'è una macchina Turing?

Question

Che cos'è una macchina Turing e perché la gente continua a menzionarla? Il mio PC IBM è tutto ciò di cui ho bisogno per fare il mio calcolo! Perché a qualcuno interessano queste macchine?

Answer 1

Il motivo per cui le macchine di Turing sono molto importanti ha a che fare con lo studio della scienza classica del calcolo o della teoria dei tipi di calcolo. Si tratta fondamentalmente dell'analisi delle proprietà generali di un computer, come ad esempio quali capacità teoriche e limitazioni ha un computer, nonché cosa intendiamo quando parliamo di & Quot; computing & Quot; qualcosa.

Un esempio di qualcosa che si potrebbe studiare usando Turing Machines è The Halting Problem . Mentre questo problema è qualcosa di un esercizio accademico, ha implicazioni facilmente tangibili nel mondo reale. Perché non scrivere un debugger che ti dirà semplicemente se il tuo programma contiene loop infiniti? The Halting Problem stabilisce che è impossibile risolvere questo problema per il caso generale.

Lo studio di Turing Machines si presta anche allo studio di grammatiche linguistiche e relative classi, il che porta allo sviluppo del linguaggio di programmazione. Il termine & Quot; espressioni regolari & Quot; nasce perché sono una grammatica regolare e lo studio di queste grammatiche (parte di Theory of Computation ) ti dirà esattamente quali tipi di problemi possono risolvere le espressioni regolari e quali no. Ad esempio, una sintassi delle espressioni regolari tradizionali non sarà in grado di risolvere il seguente problema: analizzare un numero N di caratteri 'a' nell'input, quindi analizzare lo stesso numero N di carattere 'b'.

Se sei interessato a un buon testo su questo genere di cose, dai un'occhiata a Introduzione alla teoria della computazione di Michael Sipser. Va bene.

Answer 2

La macchina di Turing è una macchina informatica teorica inventata da Alan Turing per servire da modello idealizzato per il calcolo matematico, fondamentalmente è una semplice forma di computer, è composta da un nastro (un nastro di carta ), ha una testa che può leggere i simboli, scrivere un nuovo simbolo sul posto e quindi spostarsi a sinistra o a destra.

Si dice che la macchina di Turing sia in un certo stato , e quindi un programma è un elenco di transizioni , con uno stato corrente e un simbolo sotto la testa, cosa dovrebbe essere scritto sul nastro, quale sarebbe il prossimo stato e dove dovrebbe muoversi la testa.

Ecco una Basic Turing Machine , implementata in JavaScript ...

E uno schizzo:

Answer 3

  

Il mio PC IBM è tutto ciò di cui ho bisogno per fare il mio calcolo!

Qualcosa che altri non hanno sottolineato: il tuo PC IBM è una macchina Turing. Più precisamente, è equivalente ad esso, nel senso che qualsiasi cosa il tuo PC può fare, una macchina Turing può fare, e qualsiasi cosa una macchina Turing può fare, il tuo PC può farlo.

In particolare, una macchina Turing è un modello di calcolo che cattura completamente la nozione di calcolabilità, pur rimanendo semplice da ragionare, senza tutti i dettagli specifici dell'architettura del tuo PC.

Il (generalmente accettato) " Tesi di Church-Turing " afferma che ogni dispositivo o modello di calcolo non è più potente di una macchina di Turing. Quindi, molti problemi teorici (ad esempio classi come P e NP, la nozione di & Quot; algoritmo del tempo polinomiale & Quot; e così via) sono formalmente dichiarati in termini di una macchina di Turing, sebbene, ovviamente, possono essere adattati anche ad altri modelli. (Ad esempio, a volte può essere conveniente pensare al calcolo in termini di calcolo lambda, o logica combinatoria, o altro ... sono tutti equivalenti in potenza tra loro e anche sul tuo PC IBM.)

Quindi, ecco qua: la gente parla delle macchine di Turing perché è un modo preciso e completo per dire che cosa " computer " è, senza dover descrivere ogni dettaglio dell'architettura della CPU, i suoi vincoli e così via.

Answer 4

In realtà ci sono esempi di macchine di Turing in natura. In particolare, il ribosoma , che traduce l'RNA in proteine, implementa una macchina di Turing.

Innanzitutto, alcuni retroscena:

1. L'RNA è composto da una stringa di nucleotidi (" basi ") che definiscono le lettere dell'alfabeto genetico.
2. Ci sono 4 basi nell'RNA alfabeto - A, C, G, U.
3. Le basi sono direzionali: da convenzione vengono chiamati i fini cinque primi e tre tempi (5 ', 3')
4. Una base in una stringa RNA può attrarre una base su un'altra stringa RNA tra " complementare anti-parallelo coppie " ;, dove A si attacca a U e C si attacca a G.
5. Le basi sono combinate in gruppi di 3 per formare & Quot; codoni & Quot; (Parole).
6. Ci sono 64 possibili combinazioni per i codoni (4 ^ 3).
7. ogni codone può corrispondere a un " anti-codon " ;. per esempio AUG < - > UAC
8. ci sono molecole trasportatrici speciali (" tRNA ") che hanno particolari anticodoni e sono attaccati a aminoacidi specifici (proteine).

L'operazione del ribosoma è semplice:

1. la trascrizione inizia da " start codone " ;, che definisce la lettura " ;. cornice quot &;
2. la trascrizione procede sempre nella direzione 5 '- > 3'
3. il codone sotto il frame di lettura è abbinato a un tRNA specifico contenente un amminoacido specifico
4. il codone iniziale codifica sempre il file amminoacido Metionina.
5. il nuovo amminoacido è attaccato alla proteina in crescita
6. il frame fa quindi avanzare di 3 basi al codone successivo e la proteina viene continuamente estesa
7. quando si incontra un " stop " codone, la traduzione è terminata, nessun aminoacido è attaccato e il ribosoma si dissocia dall'mRNA.

Come puoi vedere, questa è una macchina di Turing molto semplice che esegue l'operazione più complessa - la natura stessa!

Answer 5

Una macchina di Turing è una macchina teorica che può essere usata per ragionare sui limiti dei computer. In poche parole, è un computer immaginario con memoria infinita.

Ci preoccupiamo delle macchine di Turing perché ci aiutano a scoprire cosa è impossibile realizzare con computer reali (come il tuo PC IBM). Se per una macchina Turing è impossibile eseguire un determinato calcolo (come decidere il Halting Problem ), allora è logico che sia impossibile per il tuo PC IBM eseguire lo stesso calcolo.

Answer 6

Perché le persone che progettano aeroplani dovrebbero preoccuparsi dei Wright Brothers o della scienza dietro " lift " che fa volare gli aerei ad ala fissa?

Alan Turing è lodato come il padre dell'informatica moderna. La Turing Machine è il precursore di tutti i computer moderni.

The Theory of Computability è stata la mia lezione più difficile al college, ma sono contento di averlo preso. Mi ha fatto pensare a cose che non avrei mai avuto, o pensare a cose come non avrei mai fatto, e quelle sono cose buone.

Answer 7

Una macchina di Turing è una macchina astratta in grado di calcolare.

Da Wikipedia:

  

Le macchine di Turing sono dispositivi di base per la manipolazione di simboli astratti che, nonostante la loro semplicità, possono essere adattati per simulare la logica di qualsiasi algoritmo informatico. Sono stati descritti nel 1936 da Alan Turing. Le macchine di Turing non sono intese come una pratica tecnologia informatica, ma un esperimento mentale sui limiti del calcolo meccanico. Quindi non sono stati effettivamente costruiti. Studiare le loro proprietà astratte porta molte intuizioni nell'informatica e nella teoria della complessità.

     

Una macchina di Turing che è in grado di simulare qualsiasi altra macchina di Turing è chiamata macchina di Turing universale (UTM, o semplicemente una macchina universale). Una definizione più orientata alla matematica con una & Quot simile; universale & Quot; la natura fu introdotta da Alonzo Church, il cui lavoro sul calcolo lambda si intrecciava con quello di Turing in una teoria formale di calcolo nota come tesi Church-Turing. La tesi afferma che le macchine di Turing catturano effettivamente la nozione informale di metodo efficace in logica e matematica e forniscono una definizione precisa di un algoritmo o "procedura meccanica".

Answer 8

La macchina di Turing è una macchina astratta che può operare su una sequenza di dati e può cambiare il proprio stato e i dati durante il funzionamento, secondo una logica.

Questo è un concetto che costituisce la base di algoritmi, programmi memorizzati e calcolo in generale. Fornisce buoni spunti e astrazioni se hai a che fare con algoritmi, stati, dati ecc.

Spunti di riflessione, per la maggior parte.

Answer 9

Oltre alla voce di Wikipedia, potresti voler ritirare il libro The Annotated Turing di Charles Petzold. Sottotitolato & Quot; Una visita guidata attraverso il documento storico sulla computabilità di Alan Turing e la macchina di Turing & Quot ;, include il documento completo, suddiviso in blocchi con molti discorsi sull'argomento, compresa una prospettiva storica.

Answer 10

La macchina di Turing equivale a un algoritmo. Si ferma quando accetta una stringa, rifiuta o entra in un ciclo infinito quando non accetta la stringa.

Il nastro funge da memoria, le regole di transizione agiscono come condizioni 'if then else'