Section outline

  • Topics: - Turing machine (TM)

                - Turing computable function

                - 1-Turing machine

                - Simulation of (multi-tape) Turing machine by a 1-Turing machine

                - nondeterministic Turing machine (NTM)

                - Simulation of an NTM by a TM

                - recursively enumerable language (RE)

                - recursive language (REC)

    • AuGLecture12 Datei

      Slides for Lecture 12

    • SS2018_A12 Datei

      The solutions to these problems are to be presented and discussed in the Seminary on May 17.

    • SS2018_A12_SOL Datei

      This file contains solutions to selected problems from Assignment 12.