Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Verständnis Mächtigkeit Turingmaschine

+1 Punkt
171 Aufrufe
Hallo,

In Kapitel 4 der Folien wird gezeigt, dass die Mächtigkeit der Turingmaschinen die L0 Sprachen umfasst, in Kapitel 5 wird dies allerdings auf Sprachen eingeschränkt, bei denen T bei Eingabe von w hält. Was ist der Grund für diese unterschiedlichen Darstellungen?
Gefragt 13, Feb 2016 in TUR-AA von uydur uydur Lernwillige(r) (560 Punkte)  

Eine Antwort

+2 Punkte
Hallo uydur,

damit ist gemeint, dass eine zu einer bestimmten Typ 0 Sprache zugehörige Turingmaschine jedes Wort in der Sprache akzeptiert, also 1 ausgibt. Umgekehrt kann es aber sein, dass die Turingmaschine für ein Wort, dass nicht Teil der Sprache ist nicht terminiert, also nicht zwangsläufig 0 ausgibt.

Viele Grüße

Gregor (Tutor)
Beantwortet 13, Feb 2016 von uhdzw uhdzw Tutor(in) (102,490 Punkte)  
...