"sar1c" - 1 õppematerjal

SML kordamisküsimustele vastused.

masinate tabelite järgi alati koostada kompositsioonmasina tabeli. Tõestus. Olgu masinal M1 aktiivsed seisundid q1,q2,...,qk ning masinal M2 seisundid r1,r2,...rl. Kirjutame masinate M1 ja M2 tabelid teinteise järele, andes esimese masina peatumiskohtades juktimise teise masina esimesele seisundile. Selleks asendame igal pool seisundi q0 seisundiga r1, esimese masina tabeli igasse tühja lahtrisse saqb kirjutame aga sar1C. Niisugune teisendatud tabel ongi kompos.masina tabel, sest kui esimese masina töö on valmis, siis suundub täitmisjärg alati teise masina avaseisundisse. Def. 4 Olgu Turingi masinal M0 kaks passiivset seisundit 01 ja 02 . Masinat M nim masinate M1 ja M2 hargnemiseks masina M0 järgi, kui iga algkonfiguratsiooni X korral 1 0 (), 0 õ öö 01 () = 2 0 (), 0 õ - öö 02 0 (), Teoreem 2