nagroda Wolframa

W maju 2007 Stephen Wolfram ufundował nagrodę w wysokości 25000 $ dla osoby, która będzie w stanie rozsztrzygnąć problem, czy pewna prosta maszyna Turinga o dwóch stanach i trójsymbolowym alfabecie jest uniwersalna. Dla tych, którzy potrzebują pieniędzy, opisuję dalej pojęcia potrzebne do zdefiniowania problemu - są dość proste. Poniżej rzeczona maszyna zapisana graficznymi symbolami Wolframa:

Maszyna Turinga jest abstrakcyjnym modelem obliczeń stworzonym dla celów teoretycznych przez Alana Turinga w 1936 roku. Składa się ona z nieskończenie długiej taśmy podzielonej na komórki, głowicy pisząco-czytającej, wskaźnika stanu, który może wskazywać jeden z kilku stanów, oraz tabelki reguł. Maszyna pracuje wg ścisłego przepisu, przy czym jej praca podzielona jest na kolejno następujące po sobie kroki. W każdym kroku maszyna czyta symbol z komórki znajdującej się właśnie w polu widzenia głowicy, w tabelce odszukuje regułę na podstawie aktualnego stanu i przeczytanego symbolu i wykonuje określoną w tej regule akcję. Akcją może być zapisanie nowego symbolu i przesunięcie głowicy o jedną komórkę w lewo lub w prawo.

Oczywiście istnieje wiele maszyn Turinga: różnią się liczbą stanów, alfabetem symboli i zawartością tabeli reguł. Co jest jednak najciekawsze, co udowodnił Alan Turing, możliwe jest stworzenie Maszyny Uniwersalnej, która potrafi symulować każdą inną maszynę Turinga, zapisaną w odpowiedni sposób symbolicznie na jej taśmie. Taka uniwersalna maszyna została wielokrotnie jawnie zapisana, jest to względnie proste zadanie. Można także udowodnić, że wszelkie mechaniczne obliczenia da się zrealizować za pomocą maszyny Turinga - jest to więc mocne narzędzie badawcze - jeżeli udowodnimy, że jakiś system obliczeniowy jest zdolny symulować Uniwersalną Maszynę Turinga, możemy mieć pewność, że potrafi on wykonać wszystkie obliczenia, które potrafimy formalnie zapisać - tak, jak komputer.

Do dziś nie wiadomo, jaka najmniejsza maszyna Turinga może być maszyną uniwersalną. Wolfram znalazł dwustanową maszynę o alfabecie pięcioznakowym, ale nie uduwodnił, że jest najmniejsza wśród Maszyn Uniwersalnych. Co więcej, znalazł lepszą kandydatkę, ale nie potrafi rozstrzygnąć, czy jest Uniwersalna. I stąd nagroda - każdy może zgarnąć tę pulę !

Dobrymi kandydatami do nagrody mogą być na przykład autorzy i entuzjaści ezoterycznych języków programowania - często posługują się tym aparatem pojęciowym, aby wykazać, że ich języki są "Turing-kompletne". Chcąc przystąpić do konkursu, warto przejrzeć New Kind Of Science, ale także prace hobbystów - polecam ich wiki. Jeżeli ktoś dziwi się "po co to wszystko", niech pomyśli o tych pieniądzach ;-) Albo niech pomyśli o Johnie von Neumannie, który w wyniku tego typu teoretycznych rozważań wpadł na pomysł budowy maszyny liczącej, czyli komputera, którego zapewne właśnie używamy - ja - pisząc te słowa - Ty - czytając je.