Maszyna Turinga na redstone Minecraft

Implementacja maszyny Turinga z redstone'a w Minecraft

Maszyna Turinga składa się z nieskończonej taśmy z komórkami, głowicy odczytu-zapisu oraz tablicy przejść pełniącej rolę programu. W Minecraft elementy te symuluje się za pomocą redstone'a – systemu przesyłania sygnałów o 16 poziomach mocy (od 0 do 15). Pył redstone'a przesyła sygnał na odległość 15 bloków, tracąc po 1 poziomie mocy na każdy blok.

Kluczowe komponenty redstone'a:

• Pochodnia: odwraca sygnał (bramka NOT).
• Dźwignia: stabilne źródło sygnału.
• Przycisk: impuls o stałej długości.
• Przekaźnik: wzmacnia sygnał, określa kierunek i ustawia opóźnienie 1–4 ticków.
• Komparator: porównuje lub odejmuje sygnały.

Z tych elementów buduje się bramki logiczne: NOT (pochodnia), AND (dwa przekaźniki podłączone do pochodni), OR (zbiegające się przewody), NAND/NOR (kombinacje). Alfabet składa się z 4 symboli: 0, 1, pusty (ε) oraz rezerwowy.

Komórka pamięci taśmy

Komórka przechowuje 4 bity (wartości 0–15) i po aktywacji generuje ciągły sygnał. Przykład: 0101. Resetowanie odbywa się za pomocą przycisku po lewej stronie. Nadmiarowość bitów umożliwia przyszłe rozszerzenia.

Taśma składa się z 8 takich komórek, co daje łącznie 32 bity.

Rejestr przesuwny dla głowicy

Wskazuje aktualną pozycję głowicy na taśmie. Zapalona lampa oznacza bieżącą pozycję. Przyciski po prawej stronie służą do przesuwu w lewo, w prawo oraz resetu (punkt startowy to lewa lampa). Opcjonalna lampa po lewej stronie sygnalizuje zakończenie przesunięcia, minimalizując opóźnienia w cyklu.

Realizuje przesunięcia bitowe umożliwiające przemieszczanie głowicy.

Komórka programu

Przechowuje 10 bitów:

• 4 bity – wartość do zapisania.
• 2 bity – przesunięcie (10 – w lewo, 01 – w prawo).
• 4 bity – następny stan.

Sekwencja działania: zapis → przesunięcie → przejście. Program składa się z 20 komórek (4 stany × 4 symbole, w tym ε oraz stan zatrzymania/halting).

Konwerter binarno-dziesiętny (BCD)

Konwertuje adres binarny na dziesiętny, ułatwiając dostęp do poszczególnych komórek. Wejście znajduje się po prawej stronie (np. 10 → 2 po lewej). Upraszcza proces adresowania.

Cykl wykonania

Stałe opóźnienia (2 sekundy na operację) zapewniają synchronizację bez konieczności stosowania sygnałów zakończenia:

• Odczyt symbolu z komórki.
• Wyszukiwanie przejścia na podstawie stanu i symbolu.
• Zapis danych z tablicy.
• Przesunięcie głowicy.
• Przejście do nowego stanu.
• Jeśli stan halting – zatrzymanie, w przeciwnym razie kontynuacja cyklu.

Pomarańczowy przewód łączący program z cyklem przekazuje sygnał zakończenia.

Ogólna architektura

Konstrukcja integruje:

• 20 komórek programu.
• 8 komórek taśmy.
• Rejestr przesuwny.
• Cykl wykonania.
• Konwertery BCD.

Przykład: inkrementacja liczby na taśmie.

Kluczowe wnioski

• Redstone symuluje logikę maszyny Turinga za pomocą bramek logicznych i sygnałów o wartościach 0–15.
• 4-bitowe komórki z nadmiarowością bitów umożliwiają skalowanie.
• Stałe opóźnienia przyspieszają cykl działania bez konieczności stosowania sprzężenia zwrotnego.
• Alfabet 4 symboli i 4 stany generują 20 możliwych przejść.
• Układ jest w pełni funkcjonalny dla konkretnego przypadku (inkrementacja).

— Editorial Team