DEG-Graphen und Halteproblem

• Satz:

  • Sei G=(V,E) DEG-Graph.
  • Sei G der Zustandsübergangsgraph von M (M ist TM).
  • Dann ist Halteproblem für M entscheidbar

• Beweis:

  • dreiteilig

Notizen: