Tyurmits

Inom datavetenskap är Turmit en Turing-maskin som har en orientering i rymden, ett aktuellt tillstånd och ett "band" som består av en oändlig tvådimensionell uppsättning celler. Exempel på turmites är Langtons myra , definierad på cellerna i ett kvadratiskt rutnät , och Patersons maskar , definierade på kanterna av ett triangulärt rutnät .

Turmiter är likvärdiga i sin beräkningskraft med en konventionell endimensionell Turing-maskin .

Tyurmits med relativ och absolut orientering

Tyurmiter kan delas in i tyurmiter med relativ och absolut orientering. Tyurmiter med relativ orientering har en inre orientering. Kommandona i programmet innehåller en orienteringsändring i förhållande till den nuvarande: "vänster", "framåt", "höger", "vänd om". Ett exempel på en sådan turmite är Langtons myra .

Absolut orienterade Turmites, ibland helt enkelt kallade "tvådimensionella Turing-maskiner ", använder en absolut offset ("norr", etc.) i program

Exempel

Se även