W świecie maszyn Turinga, jak mierzymy „najlepszą” maszynę? Jednym ze sposobów jest gra w Pracowitego Bobra. Wyobraź sobie zawody dla wszystkich możliwych n-stanowych maszyn Turinga. Każda z nich zaczyna na nieskończonej taśmie wypełnionej zerami. Niektóre maszyny wpadną w pętlę i nigdy się nie zatrzymają. Inne zatrzymają się bardzo szybko, nie robiąc prawie nic. Nas interesują tylko te, które się zatrzymują.

W tych zawodach przyznajemy nagrody w dwóch kategoriach: produktywność i wytrzymałość. Aby to sformalizować, używamy dwóch specjalnych funkcji: Σ(n) i S(n).

Pierwsza miara, funkcja Sigma, liczy, ile jedynek maszyna zostawiła na taśmie po zatrzymaniu się. To jej „wynik”. Dla danej liczby stanów n, Σ(n) to maksymalna liczba jedynek, jaką jakakolwiek n-stanowa, 2-symbolowa maszyna Turinga może zapisać i się zatrzymać.

Reguły są proste:

1. Alfabet taśmy to tylko {0, 1}.
2. Taśma na początku jest pusta (wypełniona samymi zerami).
3. Maszyna musi się w końcu zatrzymać.

Σ(n) to po prostu najwyższy wynik uzyskany przez maszynę z n stanami, która przestrzega tych reguł. To miara jej produktywności. Więcej jedynek oznacza bardziej „produktywną” maszynę.

Rozważmy prosty przykład. Dla maszyn z jednym stanem (n=1), najwyższy możliwy wynik to jedna jedynka. Maszyna może mieć instrukcję: „w stanie 1, jeśli czytasz 0, zapisz 1, przesuń się w prawo i zatrzymaj się”. Proste. Dlatego Σ(1) = 1.

Druga miara, funkcja S, nie dba o wynik. Zamiast tego mierzy, jak długo maszyna pracuje przed zatrzymaniem. S(n) to maksymalna liczba kroków (przesunięć głowicy), jaką n-stanowa maszyna Turinga może wykonać na pustej taśmie, zanim się zatrzyma.

Jest to miara „wytrzymałości” lub złożoności czasowej maszyny. Niektóre maszyny mogą biegać po taśmie przez zadziwiająco długi czas, wykonując złożone operacje, zanim w końcu osiągną stan zatrzymania. Funkcja ta jest czasem nazywana „frantic frog”, co dobrze oddaje jej naturę chaotycznego skakania po taśmie.

Wracając do naszego przykładu n=1, maszyna, która zapisała jedną jedynkę, zrobiła to w jednym kroku. Zapisała 1, przesunęła się w prawo. Jeden krok. Dlatego S(1) = 1.

Jaka jest relacja między tymi dwiema funkcjami? Aby zapisać jedynkę, maszyna musi wykonać co najmniej jeden krok: przesunąć głowicę do komórki i zapisać symbol. Nie da się zapisać symbolu bez wykonania ruchu. Oznacza to, że liczba kroków zawsze będzie co najmniej tak duża, jak liczba zapisanych jedynek.

W praktyce, S(n) rośnie znacznie, znacznie szybciej niż Σ(n). Maszyny, które ustanawiają rekordy S(n), często wykonują miliony lub miliardy kroków, aby zapisać stosunkowo niewielką liczbę jedynek. Spędzają większość czasu na przemieszczaniu się i edytowaniu taśmy w złożony sposób.

Jak widać w tabeli, wartości rosną niewiarygodnie szybko. Obie funkcje są przykładami funkcji niewykrywalnych, co oznacza, że nie istnieje algorytm, który mógłby obliczyć ich wartość dla dowolnego n. Znalezienie tych wartości wymaga przeszukania ogromnej przestrzeni wszystkich możliwych maszyn, a dla n większego niż 4, przestrzeń ta staje się zbyt duża, aby ją w pełni zbadać.