semi entscheidbar?
Liebes Community,
kann mir bitte jemand erklären, was semi entscheidbar ist? Ich habe den unterschied mit unentscheidbar leider nicht ganz begriffen. Vielen Dank!
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik
Was semi-entscheidbar bedeutet, findet sich erklärt in einer Antwort auf Seite https://www.matheplanet.com/default3.html
Die Turingmaschine muss dann nur anhalten, wenn "entscheidbar" (könnte im nicht entscheidbaren Fall aber nie anhalten).
|
Wohingegen entscheidbar bedeutet: Es gibt eine Turingmaschine, die – auf das fragliche Problem angesetzt – anhalten wird und als Ergebnis JA oder NEIN liefert.