Turingova mašina na redstone v Minecraftu

Implementace Turingova stroje z redstonu v Minecraftu

Turingův stroj se skládá z nekonečné pásky rozdělené na buňky, čtecí a zapisovací hlavy a tabulky přechodů, která funguje jako program. V Minecraftu jsou tyto prvky simulovány pomocí redstonu – systému přenosu signálů s 16 úrovněmi síly od 0 do 15. Redstone prach přenáší signál na vzdálenost 15 bloků, přičemž na každém bloku ztrácí jednu úroveň síly.

Klíčové redstone komponenty:

• Pochodeň: invertuje signál (NOT).
• Páka: stabilní zdroj signálu.
• Tlačítko: generuje impuls pevné délky.
• Opakovač: zesiluje signál, určuje směr a nastavuje zpoždění 1–4 tiků.
• Komparátor: porovnává nebo odečítá signály.

Z těchto prvků se staví logická hradla: NOT (pochodeň), AND (dva opakovače napájející pochodeň), OR (sbíhající se dráty), NAND/NOR (kombinace). Abeceda stroje obsahuje 4 symboly: 0, 1, prázdný (ε) a rezervní.

Paměťová buňka pásky

Buňka uchovává 4 bity (hodnoty 0–15) a po aktivaci trvale vysílá odpovídající signál. Příklad: 0101. Resetování probíhá pomocí tlačítka vlevo. Bitová redundance umožňuje budoucí rozšíření.

Páska se skládá z 8 takových buněk, což dohromady dává 32 bitů.

Posuvný registr pro hlavu

Určuje aktuální pozici hlavy na pásce. Rozsvícená lampa označuje aktuální pozici. Tlačítka vpravo slouží k posunu vlevo, vpravo a resetu (počátek je u levé lampy). Volitelná lampa vlevo signalizuje dokončení posunu, čímž minimalizuje zpoždění v cyklu. Mechanismus realizuje bitové posuny pro pohyb hlavy.

Programová buňka

Uchovává 10 bitů:

• 4 bity – zapisovaná hodnota.
• 2 bity – posun (10 – vlevo, 01 – vpravo).
• 4 bity – následující stav.

Sekvence operací: zápis → posun → přechod. Program se skládá z 20 buněk (4 stavy × 4 symboly, včetně ε a stavu ukončení).

Převodník z binární do desítkové soustavy (BCD)

Převádí binární adresu na desítkovou pro přístup k jednotlivým buňkám. Vstup je vpravo (např. 10 → 2 vlevo). Zjednodušuje adresaci paměti.

Prováděcí cyklus

Pevně nastavená zpoždění (2 sekundy na operaci) zajišťují synchronizaci bez nutnosti potvrzovacích signálů:

• Přečtení symbolu z buňky.
• Vyhledání přechodu podle aktuálního stavu a symbolu.
• Zápis nové hodnoty z tabulky.
• Posun hlavy.
• Přechod do nového stavu.
• Pokud je dosaženo stavu ukončení (halting), stroj se zastaví, jinak cyklus pokračuje.

Oranžový drát vedoucí z programu do cyklu přenáší signál o ukončení běhu.

Celková architektura

Celá konstrukce integruje:

• 20 programových buněk.
• 8 paměťových buněk pásky.
• Posuvný registr.
• Prováděcí cyklus.
• BCD převodníky.

Příklad použití: inkrementace čísla na pásce.

Klíčové poznatky

• Redstone simuluje logiku Turingova stroje pomocí hradel a signálů v rozsahu 0–15.
• 4bitové buňky s redundancí umožňují snadné škálování.
• Pevná zpoždění urychlují cyklus bez nutnosti zpětné vazby.
• Abeceda o 4 symbolech a 4 stavech generuje 20 přechodů.
• Konstrukce je plně funkční pro konkrétní úlohu (inkrementace).

— Editorial Team