Def(f) rekursiv aufzählbar, f nicht berechenbar

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Def(f) rekursiv aufzählbar, f nicht berechenbar

Beitrag von Simon Siegler » 14. Mai 2009 18:31

In der Übung kam die Frage, ob es Funktionen mit rekursiv aufzählbarem Definitionsbereich gibt, die nicht berechenbar sind.

Dafür gibt es natürlich Beispiele, denn der Definitionsbereich totaler Funktionen ist rekursiv aufzählbar, die charakteristische Funktion eines nicht-entscheidbaren Problems ist also ein Beispiel.

Zurück zu „Archiv“