GThi ÜB13 Aufgabe 5 - Grundlagen der Informatik - Fachrat Informatik - Forum

Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Praktikant

Date of registration: Oct 3rd 2008

Location: Sarstedt

Saturday, August 7th 2010, 4:06pm

GThi ÜB13 Aufgabe 5

Hallo, habe Schwierigkeiten diese Aufgabe zulösen. (Genauer: ich weiss gar nicht wo ich anfangen soll)
Es müsste also eine Turingmaschiene geben, die $f^{-1}$ berechnet.
Allerdings schein die inverse funktion ja nicht überall definiert zu sein, da f nicht bijektiv ist.

Sei $f : \mathbb{N} \rightarrow \mathbb{N}$ eine injektive, berechenbare und evtl. partielle Funktion. Zeigen Sie: Die evtl partielle Funktion $f^{-1} : \mathbb{N} \rightarrow \mathbb{N}$ ist berechenbar.

hat jemand eine Idee dafür?

MfG Marc

Go to the top of the page

ThI

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

Sunday, August 8th 2010, 9:31am

Als Tipp sei vllt. Cantor'sches Diagonalisierungsverfahren gesagt?

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

Praktikant

Date of registration: Oct 3rd 2008

Location: Sarstedt

Sunday, August 8th 2010, 11:41am

Danke, bin damit auf die Cantor'sche Paarungsfunktion gekommen, die (leider unbetitelt) im Vorlesungsskript steht.

Go to the top of the page