(Theorie) Abhängige Definition von Programmen?

[Superior1337]

Hallo,

ich hoffe dieser Bereich geht für diese Frage in Ordnung, er passt meiner Meinung nach zumindest am Besten.

Es geht dabei um Programmiertheorie, beim Lernen bin ich auf eine Frage gestoßen, auf die ich in sämtlichen Unterlagen und im Netz noch keine Antwort gefunden habe.

Die Frage lautet:
"Gibt es ein Programm das immer dann undefiniert ist, wenn ein anderes Programm definiert ist oder umgekehrt?

Man solle jeweils ein Beispiel angeben oder begründen warum nicht.

Da mir kein Beispiel eingefallen ist, tendiere ich zum negativen, könnte dies aber auch nicht begründen. Und darum frage ich mal in die Runde, ob es sowas gibt und wenn ja ein Beispiel wäre klasse.

Danke im Vorraus

 

[ch40s]

Nur 'n schneller Gedanke: Halteproblem-> gibt's nicht.

 

[Superior1337]

Vorweg Danke für deine Antwort.

Das Halteproblem sagt meines wissens ja aus, dass es keinen Algorithmus gibt, der entscheiden kann, ob ein Programm nach endlich vielen Schritten terminiert oder nicht.

Aber die Assoziation zu der Fragestellung kann ich noch nicht implizieren, wieso folgt denn aus dem Halteproblem, dass kein Programm existiert, dass immer dann undefiniert ist, wenn ein anderes Definiert ist?

Sehe ich dabei einen Zusammenhang nicht?

 

[kuddlmuddl]

Obwohl ich info studiert hab sagt mir "ein Programm ist definiert" gerad nix .. was genau meisnt du damit?
Auch auf http://de.wikipedia.org/wiki/Algorithmus wirds nicht erklärt.

 

[Superior1337]

Du musst entschuldigen, die Aufgabenstellung kommt auch nicht von mir. Über die Bedeutung bin ich auch erst gestolpert, wusste ebenfalls nicht was gemeint ist. Dachte aber es läge an meiner Unwissenheit.

Also gemeint ist wohl, ob ein Programm dann nicht terminiert, wenn ein anderes Programm terminiert.

Mein bisheriger Gedanke war, dazu sagen zu können, dass wenn ein Programm einfach bei jeglicher Eingabe nicht terminiert, dass dann auch diese Existenzfrage der Aufgabe immer als wahr geschlussfolgert werden kann. Also quasi die Abhängigkeit aufgrund der schlechten Formulierung der Fragestellung außen vor lassen und sagen, ja gibt es, da dort nicht steht "genau und nur dann".

Ich denke aber diese Abhängigkeit ist schon gemeint und darauf bin ich mir unsicher.

Vorhergehende Frage war, ob es ein Programm P gibt, was nur dann definiert ist, wenn ein anderes Programm P' definiert ist. Also beide definiert in der Fragestellung.

Da habe ich überlegt, wenn man sagt P' ist ein erwartetes Argument von P, dann kann P ja nur definiert sein, wenn P' auch definiert ist. Ganz sicher bin ich mir dabei aber auch immer noch nicht.

 

[nullPtr]

Annahme, es gäbe so ein Programm, dann könntest du jedes semi-entscheidbare Problem auch co-semi-entscheiden und damit wäre es entscheidbar. Widerspruch zur Wahl des semi-entscheibaren Problems.

Beweisskizze:
Problem A ist nur semi-entscheibar (z.B. das bereits genannte Halteproblem). Implementiere semi-charakteristische Funktion als Programm. Dies liefert undefiniert, wenn ein Wort x nicht in A liegt.
Solltest du jetzt ein Programm P besitzen, dass einen definierten Wert liefern kann gdw. A undefiniert liefert, könntest du einen Entscheidungsalgorithmus bauen.

 

[Superior1337]

Sehr gut, so konnt ich das jetzt verstehen und nachvollziehen. Macht im Nachhinein auch wirklich Sinn, vielen Dank für die Hilfe.