[OT] Funzione della Macchina di Turing

[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, che invece ha la macchina di Von Neumann.

Guardate questo esempio di somma di 2 numeri con macchina di turing:

 Progettiamo una Macchina di Turing che effettui la
somma 2+3
 Lo stato iniziale del nastro su cui si muove la macchina
dovrà in qualche modo 'rappresentare' i due addendi.
 Immaginiamo dunque che sul nostro nastro tutte le celle
contengano il simbolo '0', tranne due gruppi, uno di due e
uno di tre celle, che contengono '1‘, e rappresenterano i
nostri due addendi, '2' e '3'.
 Gli addendi sono separati da una cella che contiene '0’
La testina sarà posizionata sulla prima casella che
contiene '1', e la macchina si troverà nello stato iniziale.
 La macchina dovrà fermarsi quando sul nastro, al posto dei
due gruppi di celle che contengono '1' vi sarà un solo gruppo
di cinque celle che contengono '1': questo gruppo rappresenta
il risultato, cioè il numero '5'.
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 La macchina parte nello stato 'A'. In questo stato legge '1'
(dato che questa è la sua situazione di partenza), e lo
sostituisce con '0'. Poi si sposta a destra e passa nello stato 'B'.
 Lo stato 'B' prevede istruzioni diverse a seconda che la
macchina legga '0' o '1':
 Se legge '1', vuol dire che sta ancora 'scorrendo' il primo addendo:
lascia l''1' al suo posto e si sposta ancora a destra.
 Se legge '0', vuol dire che ha finito di percorrere il primo addendo, ed è
arrivata allo '0' che lo separa dal secondo; trasformando questo '0' in '1'
ottiene il risultato di lasciare sul nastro una sequenza ininterrotta di
cinque '1‘ che rappresentano il risultato e la macchina si ferma.



Per me tutto questo non ha senso perchè a contare gli 1 messi assieme siamo noi, non la macchina.
Inoltre la macchina sa già di doversi fermare quando incontra 5 volte 1 di seguito, quindi la somma già la sa dall'inizio (almeno cosi fa capire l'esempio)

Inoltre volevo capire le differenze tra la tesi di turing e quella di church-turing.



P.S. Se l'esempio non si capisce, trovate la versione completa con i disegnini a pag 23 e 24 del pdf linkato qui sotto

http://content.yudu.com/Library/A1t1...m?referrerUrl=

[Alex'87]

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...

Inutile? Butta il computer che stai usando visto che è una macchina di Turing...

[oregon]

Originariamente inviato da Alex'87
Inutile? Butta il computer che stai usando visto che è una macchina di Turing...

[toraz]

come funziona la macchina di Turing??? a me sembra che sia un concetto inutile, boh...

La macchina di Turing e` stata uno degli strumenti fondamentali per lo studio della teoria della computabilita`.

Non ho capito come fa a elaborare dati se non possiede una ALU, che invece ha la macchina di Von Neumann.

La macchina di Turing e l'architettura (macchina) di Von Neumann non centrono niente l'una con l'altra!
La macchina di Turing e` un formalismo matematico che serve per lo studio della computabilita` degli algoritmi.
L'architettura di Von Neumann e` uno schema progettuale di base per la costruzione dei calcolatori elettronici.

La macchina di Turing e` l'interprete di un linguaggio di programmazione le cui istruzioni sono del tipo "vai avanti di una posizione", "se alla posizione corrente c'e` zero torna indietro di una posizione", eccetera, eccetera. Esistono anche implementazioni concrete della macchina, per esempio il linguaggio Brainfuck (non sono sicuro che sia proprio formalmente equivalente ma sono se non altro molto simili).

Per me tutto questo non ha senso perchè a contare gli 1 messi assieme siamo noi, non la macchina.
Inoltre la macchina sa già di doversi fermare quando incontra 5 volte 1 di seguito, quindi la somma già la sa dall'inizio (almeno cosi fa capire l'esempio)

Le macchine non fanno nulla che non gli venga detto di fare. Vengono programmate da un essere umano per svolgere un compito. In questo caso e` stata programmata per rappresentare due numeri interi (2 e 3) e per sommarli.

Inoltre volevo capire le differenze tra la tesi di turing e quella di church-turing.

La tesi di Turing da solo mi manca, quindi non saprei dirti in cosa differisce da quella di Church-Turing.

[deleted_29]

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.