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:

description of transitions of $M$
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 $δ (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: $δ (q_{1}, a) = (q_{2}, b, L) δ (q_{2}, b) = (q_{3}, c, R)$

(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 $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: $2 n$ 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, a a, a b, a c, b a, b b, b c, c a, c b, c c, \dots$

It is necessary to generate strings by length, because lexicographic order would generate infinite strings ( $a, a a, a a a, a a a a, a a a a a, \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:

generate the next binary string in proper order
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.