27 October 2007

A fost descoperita cea mai simpla masina Turing universala

O masina Turing e un computer idealizat - functioneaza fara erori si are memorie infinita. O masina Turing e universala daca poate face orice fel de calcul posibil. O reprezentare utila a masinilor Turing e urmatoarea: Fiecare rand de pe o foaie de matematica reprezinta starea memoriei masinii la un moment dat - cel mai de sus rand este primul. O patratica poate fi colorata intr-un anumit numar de culori posibile (initial exista o culoare implicita). Capul de citire poate avea si el un anumit numar de stari posibile (x, y, z, ...). O regula este o functie de culoarea patratelului pe care e capul de citire si de starea capului de citire si determina culoarea patratelului de sub capul de citire, noua pozitie a capului de citire relativa la vechea pozitie (capul se muta la stanga sau la dreapta) si noua stare a capului de citire. De exemplu o masina Turing cu 2 culori posibile si cu un cap de citire cu 3 stari posibile (x, y, z) e formata din 3x2=6 reguli. Sunt foarte multe asemenea masini Turing posibile. (Formula generala este (2nk)^nk masini Turing posibile cu n stari ale capului de citire si k culori ale memoriei.) Iata de pilda una:

 

Un program (algoritm) este un anumit input (un anumit pattern de culori) pe prima linie + pozitia initiala a capului de citire. Una dintre reguli este in mod conventional aleasa sa reprezinte comanda de oprire a programului. Patternul de culori la care s-a ajuns atunci pe ultima linie reprezinta output-ul algoritmului. (Un program care "se blocheaza" e un program care nu ajunge niciodata sa execute regula de oprire.) O masina Turing universala este o masina pe care poate fi implementat orice algoritm posibil - cu alte cuvinte o masina Turing care poate simula orice alta masina Turing. Acum a fost descoperita cea mai simpla masina Turing universala. Se stia ca nu exista nici o masina Turing universala cu 2 culori si 2 stari ale capului de citire - asa ca urmatoarea varianta candidata era 2,3. Exista 2,985,984 asemenea masini Turing posibile. In 2002, Stephen Wolfram a speculat ca poate urmatoarea masina este universala:

 

In primavara anului asta a anuntat un premiu de 25,000 de dolari celui care demonstreaza ca masina asta Turing este universala sau demonstreaza ca nu e universala. Premiul a fost luat acum de un student de 20 de ani, Alex Smith, din Birmingham.
I telephoned Alex Smith a few days ago, to tell him that we were finally convinced that he'd solved the problem and earned the prize. I asked him why he'd worked on it. He said he'd seen it as a nice puzzle. That at first he was pretty sure the Turing machine's behavior was simple enough that he could prove that it wasn't universal. But then, as he studied it, he realized that there were little bits of behavior that were more complicated. And it was with these that he managed to show universality. ... It's a very satisfying way to spend $25,000.
Asta s-ar putea sa fie un rezultat foarte important. De pilda daca Wolfram are dreptate ca universul e un calculator, regulile acestei masinii Turing sunt intr-un anumit sens legile naturii la nivelul cel mai profund (ramane sa mai determinam "doar" care este semnificatia culorilor si a starilor capului de citire). Iata care e rezultatul functionarii acestei masini Turing plecand de la un input uniform alb (fara definirea unei stari de oprire a programului):