Originariamente inviato da click1234
Salve ragazzi, qualcuno di voi ha capito come funziona la macchina di Turing??? a me sembra che sia un concetto inutile, boh...
Non ho capito come fa a elaborare dati se non possiede una ALU
la possiede, eccome, nel "programma" che ne determina il funzionamento
che invece ha la macchina di Von Neumann.
Come già detto quest'ultima è una TIPOLOGIA di macchina, ce ne sono anche altre di architettura completamente diversa (es. computer analogici)

Per me tutto questo non ha senso perchè a contare gli 1 messi assieme siamo noi, non la macchina...
In estrema sintesi l'idea di Turing (per inciso: esistono tranquillamente le sue pubblicazioni originali, e lì è interessante avere un'idea un pochino più precisa di "come" salta fuori) è quello di tagliar via tutta la croppa ad un calcolatore, per identificare il calcolatore nello stesso tempo più semplice ma più potente.

Una MdT (con nastro infinito, caratteristica fondamentale!) può computare qualsiasi "cosa" computabile (con gli approcci normali, ce ne sono altri del tutto diversi per cui ciò non è più vero).

Puoi scrivere, per una MdT, anche Windows 7.
Certo, non è proprio facilissimo, ma nulla vieta (in teoria) di farlo.
Inoltre volevo capire le differenze tra la tesi di turing e quella di church-turing.
Se intendi "tesi di church" è tutt'altra cosa, perchè è un'ipotesi di equivalenza di "potenza" descrittiva.

In sintesi per ogni funzione f: N^n -> N ricorsiva esiste una MdT che la calcola.

Mentre la Tesi di Church-Turing IPOTIZZA (non prova) che i più "potenti" formalismi (lambda calcolo etc) per la descrizione degli algoritmi NON sono più potenti delle MdT.

Ovvero che gli "altri" non riescono a calcolare quello che non riesci a calcolare con una MdT.

Attenzione che esiste un teorema che spesso viene scambiato per questa asserzione, ossia che ogni funzione calcolabile da una MdT è ricorsiva, ma si tratta di un altro aspetto (godelizzazione)

Ogni funzione calcolabile da una macchina di Turing ` e Markov-calcolabile, ricorsiva e
RAM-calcolabile.
La dimostrazione di tale teorema risulta non troppo complicata nel caso degli algo-
ritmi di Markov e dei programmi RAM (si vedano gli Esercizi 5.11 e 5.12). Nel caso
delle funzioni ricorsive, invece, la dimostrazione fa uso di una tecnica introdotta dal lo-
gico Kurt G¨ odel nella dimostrazione del suo famoso teorema e, per questo, chiamata
tecnica di goedilizzazione: tale tecnica consente di mettere in corrispondenza biunivoca e
in modo costruttivo l’insieme dei numeri naturali con quello delle configurazioni della
computazione di una macchina di Turing, simulando cos` ı attraverso funzioni ricorsive il
processo di produzione di una configurazione a partire da un’altra configurazione.