Beslisbare problemen, het Stopprobleem en de onbelisbaarheid ervan, en Universele Turingmachines Berekenbaarheidstheorie

TI2320 (IN2505-II). Berekenbaarheidstheorie.

"Some decidability results concerning finite automata and context-free languages are discussed. An informal proof of the undecidability of the Halting Problem is presented. The acceptance problem is introduced and its undecidability is demonstrated. Here the notion of Universal Turing Machine is (implicitly) used: a Turing machine can execute programmes stored with their application data on its input tape."