search

KULeuven-DeptCW / AaC-Exc

Excercise sessions of "Automata and Computability" (G0P84A).
http://onderwijsaanbod.kuleuven.be/syllabi/n/G0P84AN.htm
GNU General Public License v3.0
1 stars 3 forks source link

Taal van alle TM's #20

Open warreee opened 9 years ago

warreee commented 9 years ago

Als ik taal van TM's wil herkennen, dan maak ik een TM aan om die taal te herkennen Maar hoe zit het dan met deze laatste TM, deze wordt toch nog niet meer herkend, of gaat die wel zichzelf herkennen?

KommuSoft commented 9 years ago

Jawel, men dient enkel een encodering op te stellen voor Turing machines en deze verifieren.

Bijvoorbeeld:

Eerst m,n met m,n met m het aantal karakters in het alfabet en n het aantal toestanden. Daarna per toestand (n keer), m entries waarbij de entry eerst een getal van 1 tot n bevat (de eindtoestand) en ofwel 00, 01 of 10 afhankelijk of men link, stiltaat of rechts beweegt.

Dit kan men verifieren, en zo'n Turing machine kan dus ook zichzelf verifieren.

In heel wat boeken maakt men eerder abstractie over de encodering. Men gaat ervan uit dat elke string op een TM mapt en vice versa.