Sign inSign in

Universal Turing machine

A Turing machine UU that takes a description of a machine MM and input ww and simulates its execution.
as Michael Sipser defines itMITThe wording closest to all 5 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Opens up

Concepts that name this one as a prerequisite.

Lecturers

3

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    A Turing machine UU that takes as input an encoding of any Turing machine MM and a string WW, and simulates the execution of MM on WW.
    • 52:51Time Complexity and Universal Turing Machines
    • 21:32Hierarchy Theorems (Time, Space, and Nondeterministic)
    • 8:32Time Hierarchy Theorem
  • Blaise Agüera y Arcas

    Santa Fe Institute · Graduate

    A Turing machine that can emulate any other Turing machine by writing the rules for the computation on the tape itself.
    • 29:18Computing, Life, and Intelligence

Lectures that assume it

3

Connections

17

The lectures that define it or assume it, and the concepts next to it.

3 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.