Berechenbar -> Prädikat entscheidbar

[Mukkel]

Hallo Forum,

ich habe folgende Aufgabe:
Sei g aus Tau_1 berechenbar. Zeigen Sie, dass das Prädikat R:={(x, y) aus N² mit g(x)=y} entscheidbar ist.

Was mir noch nicht ganz klar ist was Tau_1 ist. Bei den anderen Aufgaben auf dem Blatt geht es darum zu zeigen ob eine bestimmte Funktion Primitv Rekursiv ist. Ist griechisch Tau_1 in der Literatur die Menge der PrimRek Funktionen?

Wenn ja wüßte ich nicht genau was ich machen soll. Denn alle PrimRek Funktionen terminieren ja. Die Aufgabe wäre ja dann mit einem Satz abgehakt: Alle PrimRek terminieren, somit ist g(x) entscheidbar, also ist R entscheidbar.

Vielen Dank

Mukkel

[Christoph]

Mukkel schrieb:

Die Aufgabe wäre ja dann mit einem Satz abgehakt: Alle PrimRek terminieren, somit ist g(x) entscheidbar, also ist R entscheidbar.

Würde ich auch so sehen, wenn Tau_1 die Menge der primitiv-rekursiven Funktionen ist. Ob sie das ist, weiß ich nicht. Das muss irgendwo in deinem Skript oder Buch definiert worden sein.

edit: "g(x) entscheidbar" kannst du so natürlich nicht schreiben, weil g(x) nur eine Zahl ist, aber ich denke, dass du das richtige meinst.

[Mukkel]

Ok, dann ist das mal eine leichte Aufgabe. Danke