Thema5

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

Inhaltsverzeichnis

Aufgabe 1

Definieren Sie je eine totale Funktion für den Vorgänger und die Halbierung einer natürlichen Zahl. Definieren Sie außerdem eine Funktion mit D_f = \mathbb{N}\backslash\{1234, 7266281\}.

Vorgänger f:\mathbb{N} \rightarrow \mathbb{N}

f(n) = \begin{cases} n-1, & \text{wenn } n \geq 1,\\ 0, & \text{sonst}. \end{cases}

Halbierung f:\mathbb{N} \rightarrow \mathbb{N}

f(n) = \begin{cases} \frac{n}{2}, & \text{wenn n gerade},\\ \frac{n-1}{2}, & \text{sonst}. \end{cases} D_f = \mathbb{N}\backslash\{1234, 7266281\} f(n) = \begin{cases} n, & \text{wenn } n \ne 1234,\ n \ne 7266281,\\ \perp, & \text{sonst} \end{cases}

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