This section will be about Deterministic Infinite Tape (DIT) Turing Machines (TMs). TMs are the most expressive models of computation. By most expressive we mean that whatever additional feature you give to a TM (e.g., multiple tapes, non-determinism, quantum), it will accept exactly the same set of languages as the TM you started with. It’s this expressive power that makes TMs the theoretical equivalent of the modern-day computer.

What's a Deterministic Infinite Tape Turing Machine?

An example TM

To get more familiar with DIT TMs, we will study the strings that cause a particular TM to accept, reject and loop. Note that none of the previous theoretical models of computation we saw could get “stuck” in an infinite loop.

Designing a TM which accepts a language

In this video, I show the standard approach to designing a TM which accepts a given language. More exercises at the end of this page!

Designing a TM which computes a function

The other thing that is different between TMs and the previous models of computations we’ve seen is that we can use TMs to compute functions. We say that a function is computable if there exists a TM which computes it (produces the correct output for the corresponding input in finite time).1

Exercises

Exercise. Design a Turing machine \(M\) that decides the language \[ L = \{a^n b^n : n \ge 0\}. \]

Exercise. Design a Turing machine \(M\) that decides the language \[ L = \{a^n b^{2n} c^{3n} : n \ge 0\}. \]

Exercise. Design a Turing machine \(M\) that decides the language \[ L = \{\, w \# w : w \in \{a,b\}^* \,\}. \]

Exercise. Design a Turing machine \(M\) that computes the function \[ f(1^m 0 1^n) = 1^{n \cdot m}. \] (That is, on input \(1^m 0 1^n\), the machine halts with output \(1^{n m}\) on its tape with the pointer at the beginning of the output string.)

Exercise. Design a Turing machine \(M\) that computes the function \[ \mathrm{copy}(w) = ww, \] where \(w \in \{a,b\}^*\). (That is, on input \(w\), the machine halts with output \(ww\) on its tape with the pointer at the beginning of the output string.)

  1. Really this is the definition of a total computable function, but I will not get into that here. ↩