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/tm23/solution_news.html

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

Esibizione online:
http://demonstrations.wolfram.com/TheWolfram23TuringMachine/

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... :rolleyes: Proprio minimale, eh!

[lowenz]

Eccezionale risultato per l'informatica teorica :)

[bjt2]

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

Come del resto nessuna macchina di Turing esistente!

[lowenz]

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

Come del resto nessuna macchina di Turing esistente!
E vabbè, quello è complesso assai (il problema della terminazione di un algoritmo) :D

[Siddhartha]

cosa sono gli stati e i simboli? :)

[Ziosilvio]

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/071024/full/news.2007.190.html

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 :eek:

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 (http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html)": vale a dire, quasi tutti i sistemi che non hanno un comportamento banalmente prevedibile, hanno la stessa ricchezza della macchina di Turing universale.

[Ziosilvio]

La notizia è stata riportata anche da Nature:
http://www.nature.com/news/2007/071024/full/news.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 (http://it.wikipedia.org/wiki/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 :eek:
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 (http://mathworld.wolfram.com/PrincipleofComputationalEquivalence.html)": 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]

Ehm... il link non funziona...
Sistemato :p

[Ziosilvio]

Sistemato :p
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]

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 :eek:Nah, io proverò a trovare una MdT con 2 stati e... 2 simboli e mezzo! :asd:

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

[Banus]

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 (http://www.wolframscience.com/prizes/tm23/background.html) 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 :p

[lowenz]

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 :eek:

Ora Mandrioli non potrà proporlo come tema d'esame :asd: :D