Trovata macchina di Turing universale a 2 stati e 3 simboli

[Ziosilvio]

L'annuncio è stato dato sul gruppo di discussione comp.theory.cell-automata da Tim Tyler.
Alex Smith, uno studente ventenne dell'Università di Birmingham, ha dimostrato che una certa macchina di Turing a due stati e tre simboli, descritta da Stephen Wolfram in "A New Kind of Science", è universale, ossia può riprodurre qualsiasi computazione.

Una macchina di Turing del genere è la più semplice macchina universale esistente.
È infatti noto da tempo che nessuna macchina di Turing a due stati e due simboli è universale.

Annuncio sul sito web di Wolfram:
http://www.wolframscience.com/prizes...tion_news.html

PDF con la dimostrazione:
http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf

Esibizione online:
http://demonstrations.wolfram.com/Th...TuringMachine/

Articolo in italiano su Punto Informatico:
http://punto-informatico.it/p.aspx?i=2099457

[*sasha ITALIA*]

non ne capisco nulla ma mi pare interessante... praticamente ha trovato la soluzione in hardware più semplice e più efficace per qualunque tpo di emulazione? Cosa si intende per emulazione? Far girare codice diverso tra le varie architetture?

[MaxArt]

Sasha, non ti entusiasmare troppo: è un lavoro del tutto teorico
Le "macchine di Turing" non esistono: i computer che usiamo hanno memoria ahimé finita, ma almeno usano una quantità di stati e di simboli parecchio elevata.

Certo che... porca vacca... Due stati e tre simboli... Proprio minimale, eh!

[lowenz]

Eccezionale risultato per l'informatica teorica

[bjt2]

Si, però non può risolvere il problema dell'arresto della macchina di Turing!

Come del resto nessuna macchina di Turing esistente!

[lowenz]

Originariamente inviato da bjt2

Si, però non può risolvere il problema dell'arresto della macchina di Turing!

Come del resto nessuna macchina di Turing esistente!

E vabbè, quello è complesso assai (il problema della terminazione di un algoritmo)

[Siddhartha]

cosa sono gli stati e i simboli?

[Ziosilvio]

Originariamente inviato da Siddhartha

cosa sono gli stati e i simboli?

http://it.wikipedia.org/wiki/Macchina_di_Turing
Gli stati sono le "situazioni interne" che la macchina può assumere.
I simboli, sono i caratteri che possono essere scritti, modificati e cancellati sul nastro.

[Banus]

La notizia è stata riportata anche da Nature:
http://www.nature.com/news/2007/0710....2007.190.html

Originariamente inviato da Ziosilvio

Una macchina di Turing del genere è la più semplice macchina universale esistente.
È infatti noto da tempo che nessuna macchina di Turing a due stati e due simboli è universale.

Il precedente record apparteneva a un automa cellulare scoperto da Wolfram, chiamato Regola 110, che aveva 2 stati e 5 simboli.
Immagino che questa macchina a 2 stati e 3 simboli sia la più semplice possibile... quindi segna la fine della ricerca della macchina di Turing universale minima

Penso che questo risultato sia importante più per lo studio dei sistemi complessi che per l'informatica teoria. Il fatto che anche per questo automa vale il teorema di Turing sull'incomputabilità della terminazione, implica che non è sempre possibile sapere, dato un input, quale sarà il suo comportamento asintotico. Inoltre per Wolfram è una conferma del suo "principio dell'equivalenza computazionale": vale a dire, quasi tutti i sistemi che non hanno un comportamento banalmente prevedibile, hanno la stessa ricchezza della macchina di Turing universale.

[Ziosilvio]

Originariamente inviato da Banus

La notizia è stata riportata anche da Nature:
http://www.nature.com/news/2007/0710....2007.190.html

Ottimo.

Il precedente record apparteneva a un automa cellulare scoperto da Wolfram, chiamato Regola 110, che aveva 2 stati e 5 simboli.

La regola 110 in realtà è un automa cellulare, ossia un modello di calcolo parallelo piuttosto che sequenziale.
(Ovviamente, AC e MdT si simulano a vicenda.)

Immagino che questa macchina a 2 stati e 3 simboli sia la più semplice possibile... quindi segna la fine della ricerca della macchina di Turing universale minima

Beh, si potrebbe anche provare a dimostrare che è l'unica MdT universale a 2 stati e 3 simboli.

Penso che questo risultato sia importante più per lo studio dei sistemi complessi che per l'informatica teoria. Il fatto che anche per questo automa vale il teorema di Turing sull'incomputabilità della terminazione, implica che non è sempre possibile sapere, dato un input, quale sarà il suo comportamento asintotico. Inoltre per Wolfram è una conferma del suo "principio dell'equivalenza computazionale": vale a dire, quasi tutti i sistemi che non hanno un comportamento banalmente prevedibile, hanno la stessa ricchezza della macchina di Turing universale.

Ehm... il link non funziona...
EDIT: applicata la correzione di Banus.

[Banus]

Originariamente inviato da Ziosilvio

Ehm... il link non funziona...

Sistemato

[Ziosilvio]

Originariamente inviato da Banus

Sistemato

Grazie.

Sempre rimanendo in tema: ora si potrebbe risolvere il problema simmetrico di trovare una MdT universale a 3 stati e 2 simboli.
(Se ricordo bene, ogni MdT ha una MdT equivalente a due stati e almeno tre simboli oppure a due simboli e almeno tre stati.)

[MaxArt]

Originariamente inviato da Banus

Immagino che questa macchina a 2 stati e 3 simboli sia la più semplice possibile... quindi segna la fine della ricerca della macchina di Turing universale minima

Nah, io proverò a trovare una MdT con 2 stati e... 2 simboli e mezzo!

E forse non è un'idea troppo peregrina...

[Banus]

Originariamente inviato da Ziosilvio

Sempre rimanendo in tema: ora si potrebbe risolvere il problema simmetrico di trovare una MdT universale a 3 stati e 2 simboli.

Secondo me sarebbe ancora più interessante dimostrare che non esiste una macchina di Turing universale con tre stati e due simboli: potrebbe essere interpretato come maggiore "espressività" della sequenza di simboli su nastro, rispetto allo stato della macchina.
Dalla pagina del problema leggo che Wolfram ha analizzato anche le macchine di Turing a tre stati/2 simboli usando un'euristica ma le ha trovate tutte "troppo semplici", a differenza della macchina 2,3 della quale ha chiesto la dimostrazione di universalità. Per le macchine 3,2 quindi potrebbe convenire dimostrare il contrario

[lowenz]

Originariamente inviato da Banus

Immagino che questa macchina a 2 stati e 3 simboli sia la più semplice possibile... quindi segna la fine della ricerca della macchina di Turing universale minima

Ora Mandrioli non potrà proporlo come tema d'esame