BuK/IIm12/Studenten/siclsche/Thema5

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==

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

1. für semi-entscheidbare Sprachen.

[[Bild:Siclsche_TM-Semientscheidbar.jpg.png]]

2. für entscheidbare Sprachen.

[[Bild: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.

[[Bild:Siclsche_TMkonsFkt.jpg|500px]]


== 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$$