Hamík192
30. díl – OctopusLAB
EDU_KIT1 a Turing Machine
Navazujeme na minulý článek, kde jsme popisovali WS modul s RGB svítivou diodou. Tentokrát jsme využili výpočetní kapacity ESP32 spolu se skvělými možnostmi programovacího jazyka Python a převedli jsme do EDU_KITu emulátor Turingova stroje. Proužek barevných diod nám poslouží obdobně, jako papírový (nebo magnetický) pásek ve stroji. Jednotlivé diody můžeme podle potřeby virtuálně číst i přepisovat. Popis a zdrojové kódy pro Python i MicroPython jsou tradičně na githubu:
https://github.com/octopusengine/micropython_turing-emul
Pro Python: Slouží k otestování simulace na počítači, kde se využívá knihovna turing.py a program se spouští run.py.
MicroPython: Modifikovaná knihovna pro ESP32-EK1 uturing.py a hlavní main.py, k tomu lib/pubsub.py a components/rgb.py.
Ukázky: programs_turing/*.txt (v jednoduchém textovém souboru)
Turingův stroj
Turingův stroj (Turing Machine, zkráceně TM) byl představen v roce 1936. Bylo to v době, kdy ještě neexistovaly počítače, jak je známe dnes. Pouze se experimentovalo s kombinováním mechanických a reléových přístrojů.
Koncept TM vymyslel britský matematik Alan Turing, proto obsahuje název jeho jméno. Jedná se o teoretický model „počítacího stroje“ – počítače, který definuje relativně jednoduchý abstraktní stroj. Využívá se do dneška jako úvod do stavových automatů nebo pro modelování algoritmů v teorii vyčíslitelnosti.
Představte si dlouhou pásku (TAPE), na kterou je možno zapisovat symboly (pro zjednodušení „1“ / „0“ nebo nic „_“ ). Pro představu lze použít i pásku magnetickou (podobná byla v magnetofonech, kazetách i starém videu). Magnetická páska nám umožní pomocí čtecí a zapisovací hlavy (HEAD) snadněji symboly (data) na pásce měnit (na papíře by se musely ty předchozí vygumovat).
Pak tu máme rozhodovací a řídící jednotku, která používá nějaký návod v tabulce popsaném chování (action table). Přesněji se jedná o program ve tvaru pravidel přechodové funkce (Transition fn).
Program je popisem, co se má stát, když…
TM manipuluje se symboly na pásku podle tabulky pravidel. Jedním z nejjednodušších příkladů pro TM je negace binárního čísla. Ve žluté tabulce (pomyslná „kartička“ pro uzel Q0) je velmi zkráceně popsáno (pěti znaky na řádku: „0 0 1 R 0“) -> stav n uzlu Q (karta 0), když přečtu (Read), tak zapíšu (Write), pohyb (Direction) a nový stav Q (0 nebo H). Všechny tři řádky na „kartě“ nám pak říkají:
1) Pokud je pod hlavou „1“, přepíše se na „0“ a posune se o krok dále.
2) Pokud je tam „O“, přepíše se na „1“ a posune se také.
3) Pokud se přečte „_“ (prázdný symbol), znamená to konec výpočtu a stroj se zastaví (přechodem do QH/ HALT / stop).
Na pásce by se nám z „0110_…“ stalo „1001_…“.
Na obrázku jsou naznačeny i další stavy (Q1, Q2, ..Qn) a jejich karty. Ty ale v popsaném příkladu nevyužíváme. Ze stavu Q0 se totiž dostaneme pouze do pomyslného QH, což je zastavení výpočtu (a proto také nemá svou samostatnou kartu).
Šachy, GO a programování TM
Naučit se hrát šachy znamená v první řadě naučit se, jak se dané figurky mohou pohybovat a k tomu nějaká další pravidla hry. V případě programovacího jazyka je to jeho syntaxe (jak ho správně psát) a k tomu patří i „umění“ algoritmizace. Možná tušíte, že naznačuji rozdíl v „umět hrát šachy“ a UMĚT hrát šachy (hrát lépe, než někdo jiný). Stát se opravdu skvělým hráčem vyžaduje i trochu nadání ale především neustálé praktické zdokonalování.
Podobně je to s programováním: umět programovat a UMĚT programovat – jsou dost odlišné pojmy.
Znáte hru GO? Je to desková hra, která má podstatně jednodušší pravidla, než šachy. Dva hráči střídavě kladou své kameny na hrací desku (průsečíky mřížky) a používají velmi jednoduché pravidlo, za jakých podmínek které kameny na desce mohou zůstat. Vřele vám tuto hru doporučuji!
Hra má jen černé a bílé kameny a opravdu jednoduchá pravidla – a přitom počítačový program porazil hráče šachů o mnoho let dříve. Možnosti strategie jsou totiž v GO mnohem rozsáhlejší. No a porozumět programům pro Turingův stroj, je jako naučit se hrát GO. Ale naučit se TM programovat, je jako naučit se dobře hrát GO. Může to vypadat jednoduše, ale pro zvládnutí problematiky se neobejdete bez vytrvalého postupného praktického zdokonalování.
odložené odkazy – pod čarou:
Emulator
Pythonprograms_turing/... turing.py run.py
MicroPythonprograms_turing/... lib/pubsub.py components/rgb.py uturing.py main.py
program_file
The program is loaded as a text file (programs_turing/program.txt) where each line represents a transition function of the form fn(p,X)=(Y,D,q), so the 5 tuples are strictly in the order p, X, Y, D, q (the character _ represents a blank symbol on the tape)
Instagram – fotka + video:
https://www.instagram.com/p/CII1cC8LQg9/
https://www.instagram.com/p/CIIxMp4HWZy/