TURINGŮV
STROJ

 

 

Program AlanMath (zkratka z Alan Mathison Turing) interpretuje popisy Turingova stroje. Např. Turingův stroj akceptující množinu všech řetězců

COPIES("a", N) || COPIES("b", N), for N >= 0,

může být popsán takto

Begin End # 1
Begin # # End R
Begin a A 2 R
2 B B 2 R
2 a a 2 R
2 b B 3 L
3 B B 3 L
3 A A 5 R
3 a a 4 L
4 a a 4 L
4 A A Begin R
5 B B 5 R
5 # # End R

Obrázek 1.

První řádek popisu obsahuje

Start Stop Delta Hlava [případná poznámka]

 Start   - jméno výchozího stavu
 Stop   - jméno koncového stavu
 Delta   - znak, užívaný jako speciální prázdný symbol
  (ne však mezera)
 Hlava   - číslo, počáteční pozice hlavy na pásce

Následuje tabulka, vlastně program, jejíž každý řádek popisuje jeden krok činnosti Turingova stroje. Řádek má obecně tvar:

Stav Symbol NovýSymbol NovýStav Kam [případná poznámka]

 Stav   - jméno momentálního stavu
 Symbol   - znak, který se právě nalézá pod hlavou
 NovýSymbol   - znak, který se zapíše na pásku
 NovýStav   - jméno následujícího stavu, do něhož stroj přechází
 Kam   - směr kam se hlava přesune:
  "R" do prava, "L" do leva

Existuje mnoho definic Turingova stroje. Ta právě uvedená odpovídá knize Zohara Manny Matematická teorie programů, SNTL, Praha, 1981. AlanMath bude možná nutné trochu pozměnit, budete-li jej chtít využít jako studijní pomůcku při práci s jinou učebnicí. Když ASCII soubor OBRAZEK1.TXT obsahuje popis z Obrázku 1 pak program AlanMath na Obrázku 2 s hodnotou argumentu OBRAZEK1.TXT zobrazí průběh výpočtu a napíše "Akceptováno" pro vstupní řetězec "aaabbb"; napíše "Zamítnuto" pro vstupní řetězec "aaabb".

/* AlanMath */
TM = ARG(1)
parse value LINEIN(TM) with Start Stop Delta Hlava .
T. = ""
/* 5-tice jsou Stav Symbol NovySymbol NovyStav Kam */
do while LINES(TM) > 0
  parse value LINEIN(TM) with Stav Symbol T.Stav.Symbol
end
Paska. = Delta; Film = ""
say "Zadej vstupní řetězec"; parse pull Vstup .
do J = 1 to LENGTH(Vstup)
  Paska.J = SUBSTR(Vstup, J, 1); Film = Film || Paska.J
end
say COPIES(" ", Hlava - 1) ||"_"; say Film "v" Stav
Stav = Start; Symbol = Paska.Hlava
do until Stav = Stop | T.Stav.Symbol = ""
  parse var T.Stav.Symbol Paska.Hlava Stav Kam .
  Film = OVERLAY(Paska.Hlava, Film, Hlava, 1)
  if Kam = "L" then Hlava = Hlava - 1; else Hlava = Hlava + 1
  if Hlava = 0 then leave
  Symbol = Paska.Hlava
  say COPIES(" ", Hlava - 1) || "_"; say Film "v" Stav
end
if Stav = Stop then say "Akceptováno"; else say "Zamítnuto"

Obrázek 2

Následující obrázek ukazuje průběh výpočtu v případě vstupního řetězce "ab" v prostředí Personal REXX for Windows(tm) Version 3.50, Quercus Systems:

           Průběh výpočtu


hlavní stránka english

změněno 26. dubna 2002
Copyright © 1998-2002 Vladimír Zábrodský