Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Berechenbarkeit
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Berechenbarkeit
HardiB
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.10.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-11-08


Hallo,
folgende Aufgabe

Sei $f$ die "nirgends definierte" Funktion und h(x)=4 für alle $x \in N$. Ferner sei $g$ eine beliebige totale Funktion, die nicht Turing-berechnbar ist.
Dann gilt:
1) Die Funktion g(h(x)) kann LOOP-berechenbar sein.
2) Die Funktion g(h(x)) ist Turing-berechenbar.
3) Die Funktion f(g(x)) ist Turing-berechenbar.
Warum ?


Meine Idee:
1) Jede LOOP-berechenbare Funktion ist total und somit kann jede totale Funktion LOOP-berechenbar sein, muss aber nicht. Daran ändert sich auch nichts, wenn wir eine Komposition mit einer Konstanten Funktion bilden, denn die Komposition bleibt in dem Fall auch total, somit könnte die Komposition LOOP-berechenbar sein.

Die nächsten zwei machen für mich wenig sinn.
2) Haben wir wie im ersten Fall eine Komposition, die total ist, aber nicht jede totale Funktion ist Turing-berechnbar oder?
3) Eine Totale Funktion in einer nicht Turing-berechenbaren Funktion, kann Turing-berechenbar sein, aber muss sie dass wirklich?

Über eure Hilfe wäre ich sehr dankbar.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-11-08


Hallo HardiB,

wie lautet die genaue Aufgabenstellung?

mfg
thureduehrsen


-----------------
sammeltlemmas.blogspot.de/

https://www.informatik.uni-kiel.de/~tdu/



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
HardiB
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.10.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-11-08


Hallo,
die Aufgabenstelung lautet
Sei f die "nirgends definierte" Funktion und h(x)=4 für alle x∈N. Ferner sei g eine beliebige totale Funktion, die nicht Turing-berechnbar ist.
Welche der der Antworten treffen zu
1) Die Funktion g(h(x)) kann LOOP-berechenbar sein.
2) Die Funktion g(h(x)) ist Turing-berechenbar.
3) Die Funktion f(g(x)) ist Turing-berechenbar.
4) Die Funktion g ist WHILE-berechnenbar

Nach der Musterlösung sind 1-3 Korrekt (die 4 ist ja klar falsch) und meine Frage wäre warum, denn ich kann mit nur 1 erklären?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Zwerg_Allwissend
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 248
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-11-10


2020-11-08 19:04 - HardiB in Beitrag No. 2 schreibt:
Hallo,
die Aufgabenstelung lautet
Sei f die "nirgends definierte" Funktion und h(x)=4 für alle x∈N. Ferner sei g eine beliebige totale Funktion, die nicht Turing-berechnbar ist.
Welche der der Antworten treffen zu
1) Die Funktion g(h(x)) kann LOOP-berechenbar sein.
2) Die Funktion g(h(x)) ist Turing-berechenbar.
3) Die Funktion f(g(x)) ist Turing-berechenbar.
4) Die Funktion g ist WHILE-berechnenbar

Nach der Musterlösung sind 1-3 Korrekt (die 4 ist ja klar falsch) und meine Frage wäre warum, denn ich kann mit nur 1 erklären?

Ersetzte überall h(x) durch 4. Dann

1) Mit 4 € Def(g) gilt g(4) = irgendeine Konstante c (denn g ist total) und folglich ist g(h(x)) LOOP-berechenbar. Unklar warum da "kann" steht. Achtung: Der Beweis ist unkonstruktiv, da c nicht bekannt ist. D.h., man weiß, daß es ein LOOP-Programm für g(h(x)) gibt, kann dieses aber nicht konkret hinschreiben.

2) Weil LOOP-berechenbar.

3) Wenn die Berechnung von g(x) gelingt, dann f(g(x)) = undefiniert (denn f ist "nirgends definierte" Funktion). Andernfalls gilt ebenfalls f(g(x)) = undefiniert, denn um f(g(x)) für ein konkretes x zu berechenen muß die TM zunächst g(x) berechnen. Da diese Berechnung nicht terminiert, terminiert die Berechnung von f(g(x)) erst recht nicht. Damit f(g(x)) = f(x) f.a. x.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
HardiB
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 31.10.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-11-12


Hallo Zwerg_Allwissend,
sry für die späte Antwort.

Zu 1) du nimmst dir hier irgendwie heraus zu sagen, dass totale Funktion => Loop-Berechenbarkeit, dies sollte aber eigentlich nicht stimmen, deshalb das "kann"?

2) Wenn "g(h(x)) kann LOOP-berechenbar sein" dann müsste doch hier auch ein "kann" stehen?

zu 3) Ich nehme an, f.a. steht für falsche Antwort? Leider stimmen die Lösungen tatsächlich, warum auch immer. Sind nämlich schon seit Jahren bei uns an der im Umlauf und dieses Jahr wieder, leider gibt es bei uns gerade keine Möglichkeit den Dozenten etc zu kontaktieren, deswegen fragte ich btw auch hier.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3251
Wohnort: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-11-12


2020-11-12 12:04 - HardiB in Beitrag No. 4 schreibt:
Zu 1) du nimmst dir hier irgendwie heraus zu sagen, dass totale Funktion => Loop-Berechenbarkeit, dies sollte aber eigentlich nicht stimmen, deshalb das "kann"?
Nein, das Argument ist: konstante Funktion => Loop-berechenbar. Es gilt g(h(x)) = g(4) für alle x, also ist das eine konstante Funktion. Man weiß vielleicht nicht unbedingt, wie diese konstante Funktion genau aussieht, weil man dazu g(4) bestimmen müsste, was jedenfalls nicht mithilfe einer Turing-Maschine geht, aber das spielt keine Rolle. Die Definition von Loop-Berechenbarkeit sagt ja nur: g(h(x)) ist Loop-berechenbar, wenn ein Loop-Programm existiert, das für jedes x den Wert g(h(x)) berechnet. Das ist mit unkonstruktiv gemeint.


2) Wenn "g(h(x)) kann LOOP-berechenbar sein" dann müsste doch hier auch ein "kann" stehen?
Das mit dem "kann" bei 1) ist aus meiner Sicht Unsinn (außer um einen aufs Glatteis zu führen).


zu 3) Ich nehme an, f.a. steht für falsche Antwort? Leider stimmen die Lösungen tatsächlich, warum auch immer. Sind nämlich schon seit Jahren bei uns an der im Umlauf und dieses Jahr wieder, leider gibt es bei uns gerade keine Möglichkeit den Dozenten etc zu kontaktieren, deswegen fragte ich btw auch hier.
f.a. steht für "für alle".

Das Argument von Zwerg_Allwissend ist mir bei 3) zu unsauber. Dass g nicht Turing-berechenbar ist, heißt, dass keine Turing-Maschine existiert, die g berechnet. Man kann also nicht versuchsweise einen Wert von g berechnen und gucken, ob das irgendwie gelingt. Dazu müsste man erst eine Art berechenbarer Unterfunktion g' von g definieren, die mit g in einigen Werten übereinstimmt und sonst undefiniert ist, und vielleicht maximal mit dieser Eigenschaft ist. 🤔
Diese Überlegung kann man sich aber sparen, denn f(g(x)) ist bereits aufgrund von elementaren Überlegungen die nirgends definierte Funktion, und damit mit f identisch.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Zwerg_Allwissend
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.12.2013
Mitteilungen: 248
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-11-13


2020-11-12 12:50 - ligning in Beitrag No. 5 schreibt:
Das Argument von Zwerg_Allwissend ist mir bei 3) zu unsauber. Dass g nicht Turing-berechenbar ist, heißt, dass keine Turing-Maschine existiert, die g berechnet. Man kann also nicht versuchsweise einen Wert von g berechnen und gucken, ob das irgendwie gelingt.

Ja, da hast Du recht. Man kann wie bei (1) argumentieren: Für jedes x ist g(x) irgendeine natürliche Zahl und damit f(g(x)) = f(x) mit der Definition von f. Die Eigenschaft "g total" braucht man im Übrigen nicht, denn wenn g(x) = undef dann natürlich auch f(g(x)) = undef = f(x).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]