Entscheidbarkeit - Versionsgeschichte

Jana: /* Aufzählbare Sprachen */

2018-08-29T09:33:21Z

‎Aufzählbare Sprachen

2018-08-27T14:21:23Z

‎Beispiel: Das Post'sche Korrespondenzproblem

2018-08-26T22:49:11Z

‎Beispiel: Das Post'sche Korrespondenzproblem

2018-08-15T12:11:26Z

‎Semi-Entscheidbare Sprachen

2018-08-15T12:10:00Z

2018-08-14T22:42:51Z

‎Semi-Entscheidbare Sprachen

2018-08-14T22:41:23Z

2018-08-14T22:40:44Z

2018-08-14T22:33:42Z

‎Semi-Entscheidbare Sprachen

2018-08-14T22:29:03Z

‎Semi-Entscheidbare Sprachen

@@ Zeile 47: / Zeile 47: @@
      Rst: R[0] := 0
      R[1]++
 Der Algorithmus probiert alle $T_i^k$ durch, in der Reihenfolge $T_0^0, T_0^1, T_1^1, \ldots$.

@@ Zeile 100: / Zeile 100: @@
 Lösung:(1)(3)(2)(3)
 Keine Lösung gibt es zB für:
@@ Zeile 118: / Zeile 120: @@
 Gegeben eine Menge $K$ von Paaren $(x_i,y_i)$ aus nichtleeren Wörtern über einem Alphabet $\Sigma$. Es soll entschieden werden ob eine ''korrespondierende Folge'' von Indizes $i_2,...,i_n \in {1,...,k}, n \geq 1$ gibt, so dass $x_1,...,x_(i_n) = y_1,...,y_(i_n)$.
 [[Kategorie:TODO]]

@@ Zeile 86: / Zeile 86: @@
 == Beispiel: Das Post'sche Korrespondenzproblem ==
-'''TODO'''
+Gegeben eine Menge an Dominosteinen bei denen jeweils oben und unten eine Zeichenkette steht, gibt es eine Folge an Dominos, so dass die Konkatenation der Ketten oben und unten gleich sind? (Dabei dürfen Steine mehrmals verwendet werden.)
 [[Kategorie:TODO]]

@@ Zeile 77: / Zeile 77: @@
      goto Start
-     Tr: True
+     Tr: return True
-     Fa: False
+     Fa: return False
 Dieser Algorithmus terminiert garantiert.

← Nächstältere Version		Version vom 15. August 2018, 12:10 Uhr
Zeile 83:		Zeile 83:

	'''Korollar:''' Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.		'''Korollar:''' Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.
		+
		+	== Beispiel: Das Post'sche Korrespondenzproblem ==
		+
		+	'''TODO'''

	[[Kategorie:TODO]]		[[Kategorie:TODO]]

← Nächstältere Version		Version vom 14. August 2018, 22:42 Uhr
Zeile 81:		Zeile 81:

	Dieser Algorithmus terminiert garantiert.		Dieser Algorithmus terminiert garantiert.
		+
		+	'''Korollar:''' Die Menge der nicht terminierenden Turingmaschinen ist nicht semi-entscheidbar.

	[[Kategorie:TODO]]		[[Kategorie:TODO]]

@@ Zeile 36: / Zeile 36: @@
 '''Beweis:''' Die Idee ist, einfach alle $n$-tupel $(x_1,\ldots,x_n)$ durchzuprobieren, und die, für die es passt, auszugeben.
-'''TODO'''
+'''Satz:''' Die Menge der terminierenden Turingmaschinen $\frak T$ ist aufzählbar.
 == Semi-Entscheidbare Sprachen ==
@@ Zeile 69: / Zeile 81: @@
 Dieser Algorithmus terminiert garantiert.
 [[Kategorie:TODO]]

← Nächstältere Version		Version vom 14. August 2018, 22:40 Uhr
Zeile 74:		Zeile 74:
	'''Beweis:''' Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:		'''Beweis:''' Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:

		+	Start: if T[R[0],R[1]] == ‾\|‾ then print R[0]
		+	R[0]++
		+	if R[0] > R[1] then goto Rst
		+	goto Start
		+
		+	Rst: R[0] := 0
		+	R[1]++

		+	Der Algorithmus probiert alle $T_i^k$ durch, in der Reihenfolge $T_0^0, T_0^1, T_1^1, \ldots$.

	[[Kategorie:TODO]]		[[Kategorie:TODO]]

← Nächstältere Version		Version vom 14. August 2018, 22:33 Uhr
Zeile 69:		Zeile 69:

	Dieser Algorithmus terminiert garantiert.		Dieser Algorithmus terminiert garantiert.
		+
		+	'''Satz:''' Die Menge der terminierenden Turingmaschinen $\frak T$ ist aufzählbar.
		+
		+	'''Beweis:''' Bezeichne $T_i$ die durch $i\in\mathbb{N}$ codierte Turingmaschine. Offensichtlich ist entscheidbar, ob $T_i$ nach $k$ schritten terminiert: Man muss $T_i$ nur $k$ schritte simulieren, und schauen, ob sie in dieser Zeit terminiert. Sei $T_i^k = \top$, falls $T_i$ nach höchstens $k$ schritten terminiert, und $T_i^k = \bot$ sonst. Dann zählt folgender Algorithmus alle terminierenden Turingmaschinen auf:
		+
		+

	[[Kategorie:TODO]]		[[Kategorie:TODO]]

@@ Zeile 58: / Zeile 58: @@
 '''Lemma:''' Eine Sprache $\frak L$ ist genau dann entscheidbar, wenn sowohl $\frak L$ als auch $\overline{\frak L}$ semi-entscheidbar sind.
-'''Beweis:''' "$\rightarrow$" ist
+'''Beweis:''' "$\Rightarrow$" ist trivial. "$\Leftarrow$": Seien $M : \mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ und $\overline{M}:\mathbb{N}\rightarrow\{\bot\}\cup{\frak L}$ entsprechend gegeben. Dann entscheidet folgendes Programm $\frak L$:
 [[Kategorie:TODO]]