Skip to content

Fragen

  • Satz von Rice
  • Das heisst doch, dass eine Menge von entscheidbaren Funktionen unentscheidbar ist?
  • Für was werden Loop/While/... Programme benötigt? Und wieso sind sie so restriktiv (z.B. \(x_0=x_1+x_2\) ist nicht erlaubt, obwohl es mit einem Loop-Programm selbst machbar ist)?
  • Eine Frage wegen der Entscheidbarkeit vom Halteproblem: Wie passen die folgende zwei Folien zusammen:

img

und

img

und

img

Laut den Folien ist das Spezielle Halteproblem, das Halteproblem und das leere Halteproblem semi-entscheidbar, weill H0 semi entscheidbar ist und nicht entscheidbar weil Hs nicht entscheidbar ist.

  • Nicht-Entscheidbar = Es ist nicht entscheidbar, könnte aber semi-entscheidbar sein
  • Unentscheidbar = Es hält nie an

  • In der Folien werden die Begriffe als Synonyme verwendet

  • "So kann auch komplement von M nicht nach (1) semi-entscheidbar sein"?

Wenn NP=P ist, dann könnten alle NP-Probeleme deterministisch in Polynomzeit gelöst werden.