La Macchina di Turing Universale(2,3) di Wolfram funziona!

In questi giorni sto studiando (beh più che altro sto leggendo) Calcolabilità e Complessità, giusto oggi cercavo in rete degli approfondementi sulla Macchina di Turing e sono giunto, passando dal blog di Alfredo Panzera, sul sito della Wolfram Research in cui ho letto che un ragazzo di 20 anni, Alex Smith, ha dimostrato il corretto funzionamento della Macchina Universale a 2 stati e 3 colori descritta da Stephen Wolfram (che già ne aveva dimostrata una a due stati e cinque colori nel libro A New Kind of Science) ma non dimostrata. Ciò significa che questa è la macchina di Turing “più piccola” possibile.

Per la dimostrazione della validità la Wolfram’s Research aveva messo in palio un premio da 25.000$

Per maggiori informazioni:

Rispondi