Skip to content

15. UTM & Enumerators

Feb 24, 2022

Universal Turing Machine

Limitations of TMs:

  • TMs are "hardwired" to execute only one program
  • real programs are re-programmable
  • Universal machine needs to be able to execute other TMs (~ operating system)

Universal TM is reprogrammable and can simulate any other Turing machine, \(M\).

Inputs of a UTM:

  1. description of transitions of \(M\)
  2. input string of \(M\)

Assume UTM is a 3-tape machine (for convenience - can do the same with 1 tape):

  • Tape 1: description of M: describe \(M\) as a string of symbols (binary string)
  • Tape 2: tape contents of M
  • Tape 3: state of M

Encoding

Unary encoding example:

Alphabet encoding

1
a : 1    b : 11   c : 111    d : 1111     etc.

Head movement encoding

1
Move L: 1     Move R: 11

Transition encoding

Transition \(\delta(q_1, a) = (q_2, b, L)\) => encoding: 10101101101

1
2
3
q1     a     q2     b      L
 🠗     🠗      🠗      🠗      🠗
 1  0  1  0  11  0  11  0  1

where 0 is used as separator character.

Multiple transitions:   \(\delta(q_1, a) = (q_2, b, L) \quad \delta(q_2,b)=(q_3, c, R)\)

1
2
3
4
5
(q1,a) = (q2,b,L)    (q2,b) = (q3,c,R)
    🠗                      🠗      
 10101101101    00    1101101110111011
                 🠕
             separator

=> Tape 1 is a finite binary encoding of machine \(M\): 1010110110100110110111011101100...

Language of TMs

Since Turing machine is described with a binary string, the set of TMs forms a language: each string of this language is the binary encoding of a Turing machine.

\(L = \{1010110101, 101011101011, \dots \}\)

All machines can be encoded, listed, ordered, etc. in this language of all machines.

This set is countable => TMs are countable.

Proving countability

  • Infinite sets are either countable or uncountable
  • TM-recognizable languages are countable
  • all possible languages for finite alphabet are uncountable

=> there are many more languages than TMs
=> not all languages have corresponding TM

Non-Recognizable Languages = languages that have no TM that recognizes them.

For a countable set, there is 1-to-1 correspondence with \(\mathbb{N}\): every element of the set is mapped to a positive integer, such that no two elements are mapped to the same integer.

Examples:

  • even integers are countable: \(2n\) corresponds to \(n+1\)

  • rational numbers are countable (by diagonalization) => proof by describing enumeration procedure that corresponds to natural numbers

Enumerator

Definition. Let \(S\) be a set of strings (language). An enumerator for \(S\) is a Turing machine that generates (prints on tape) all the strings of \(S\), one by one *and* each string is generated in finite time.

=> enumerator produces the elements of \(L\) in order.

Enumerator is an infinite algorithm (infinite loop) whose job is to write output in order, producing each output element in finite time.

We can create an enumerator as a TM.

Observation: if for set \(S\) there is an enumerator, then the set is countable. Enumerator describes the correspondence of \(S\) to natural numbers.

Example

The set of strings \(S = \{a,b,c \}^+\) is countable.

Approach: describe an enumerator for \(S\). How to design this algorithm?

Solution: Generate all possible strings by length in canonical order (proper order):

\(a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, \dots\)

It is necessary to generate strings by length, because lexicographic order would generate infinite strings (\(a,aa,aaa,aaaa,aaaaa,\dots\))

TMs are countable

All TMs can be encoded as binary strings => find enumeration procedure for the set of TM strings to prove TMs are countable.

Enumerator approach:

Repeat infinitely:

  1. generate the next binary string in proper order

  2. check if the string describes a valid TM

    • if yes: print output
    • if no: ignore string

=> This enumerator will produce as its output all possible TMs.

Simpler proof:

Each TM binary string is mapped to the number representing its value.