Thema5

Aus ProgrammingWiki
< BuK < IIm12 < Studenten < siclsche
Archivierte Version vom 2013-04-25T11:03:05+00:00. Aktuelle Version

Aufgabe 1

Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:

1. für semi-entscheidbare Sprachen.

Siclsche_TM-Semientscheidbar.jpg.png

2. für entscheidbare Sprachen.

Siclsche_TM-Entscheidbar.jpg.png

Aufgabe 2

Entwickeln Sie eine Turing-Maschine, welche die konstante Funktion f(x)=5 für alle x\in\mathbb{N} berechnet.

Siclsche_TMkonsFkt.jpg


Aufgabe 3

Für K = ((001,0),(01,011),(01,101),(10,001)) gibt es eine Lösung. Die gesuchte Indexfolge heißt:

(2 \ 4 \ 3 \ 4 \ 4 \ 2 \ 1 \ 2 \ 4 \ 3 \ 4 \ 3 \ 4 \ 4 \ 3 \ 4 \ 4 \ 2 \ 1 \ 4 \ 4 \ 2 \ 1 \ 3 \ 4 1 \ 1 \ 3 \ 4 \ 4 \ 4 \ 2 \ 1 \ 2 \ 1 \ 1 \ 1 \ 3 \ 4 \ 3 \ 4 \ 1 \ 2 \ 1 \ 4 \ 4 \ 2 \ 1 \ 4 \ 1 1 \ 3 \ 4 \ 1 \ 1 \ 3 \ 1 \ 1 \ 3 \ 1 \ 2 \ 1 \ 4 \ 1 \ 1 \ 3)

Überprüfen Sie die angegebene Lösung per Hand.


Lösung für beide:

01100110100100101100110011010011010010011010010010110001001011010100100101 00100100101100110001010011010010011000100101100010010100100101001010011000100101

für x:

01 \ 10 \ 01 \ 10 \ 10 \ 01 \ 001 \ 01 \ 10 \ 01 \ 10 \ 01 \ 10 \ 10 \ 01 \ 10 \ 10 \ 01 \ 001 \ 10 \ 10 \ 01 \ 001 \ 01 \ 10 001 \ 001 \ 01 \ 10 \ 10 \ 10 \ 01 \ 001 \ 01 \ 001 \ 001 \ 001 \ 01 \ 10 \ 01 \ 10 \ 001 \ 01 \ 001 \ 10 \ 10 \ 01 \ 001 \ 10 \ 001 001 \ 01 \ 10 \ 001 \ 001 \ 01 \ 001 \ 001 \ 01 \ 001 \ 01 \ 001 \ 10 \ 001 \ 001 \ 01

für y:

011 \ 001 \ 101 \ 001 \ 001 \ 011 \ 0 \ 011 \ 001 \ 101 \ 001 \ 101 \ 001 \ 001 \ 101 \ 001 \ 001 \ 011 \ 0 \ 001 \ 001 \ 011 \ 0 \ 101 \ 001 0 \ 0 \ 101 \ 001 \ 001 \ 001 \ 011 \ 0 \ 011 \ 0 \ 0 \ 0 \ 101 \ 001 \ 101 \ 001 \ 0 \ 011 \ 0 \ 001 \ 001 \ 011 \ 0 \ 001 \ 0 0 \ 101 \ 001 \ 0 \ 0 \ 101 \ 0 \ 0 \ 101 \ 0 \ 011 \ 0 \ 001 \ 0 \ 0 \ 101