La notizia è stata riportata anche da Nature:
http://www.nature.com/news/2007/0710....2007.190.html
Quote:
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.