Busch Complexity Lectures:

Turing’s Thesis

Costas Busch - LSU 1

Turing’s thesis (1930):

Any computation carried out

by mechanical means
can be performed by a Turing Machine

Costas Busch - LSU 2

Algorithm:
An algorithm for a problem is a
Turing Machine which solves the problem

The algorithm describes the steps of

the mechanical means

This is easily translated to computation steps

of a Turing machine

Costas Busch - LSU 3

When we say: There exists an algorithm

We mean: There exists a Turing Machine

that executes the algorithm

Costas Busch - LSU 4

 Variations
of the
Turing Machine

Costas Busch - LSU 5

 The Standard Model
Infinite Tape
◊ ◊aab abb cac a◊◊◊

Read-Write Head (Left or Right)

Control Unit

Deterministic

Costas Busch - LSU 6

 Variations of the Standard Model

Turing machines with: • Stay-Option

• Semi-Infinite Tape
• Multitape
• Multidimensional
• Nondeterministic

Different Turing Machine Classes

Costas Busch - LSU 7
Same Power of two machine classes:
both classes accept the
same set of languages

We will prove:
each new class has the same power
with Standard Turing Machine

(accept Turing-Recognizable Languages)

Costas Busch - LSU 8

Same Power of two classes means:

for any machine M1 of first class

there is a machine M2 of second class

such that: L ( M1 ) = L ( M 2 )
and vice-versa

Costas Busch - LSU 9

Simulation: A technique to prove same power.
Simulate the machine of one class
with a machine of the other class

Second Class
First Class Simulation Machine
Original Machine M2
M1 M1

simulates M1
Costas Busch - LSU 10
Configurations in the Original Machine M1
have corresponding configurations
in the Simulation Machine M 2

M1
Original Machine: d 0 ≻ d1 ≻ " ≻ d n

∗ ∗ ∗
Simulation Machine: d 0ʹ ≻ d1ʹ ≻ " ≻ d nʹ
M2
Costas Busch - LSU 11
 Accepting Configuration

Original Machine: df

Simulation Machine: d ʹf

the Simulation Machine

and the Original Machine
accept the same strings
L ( M1 ) = L ( M 2 )
Costas Busch - LSU 12
 Turing Machines with Stay-Option

The head can stay in the same position

◊ ◊aab abb cac a◊◊◊

Left, Right, Stay

L,R,S: possible head moves

Costas Busch - LSU 13
Example: Time 1
◊ ◊aab abb cac a◊◊◊
q1
Time 2
◊ ◊b ab abb cac a◊◊◊
q2

q1 a → b, S q2
Costas Busch - LSU 14
Theorem: Stay-Option machines
have the same power with
Standard Turing machines

Proof: 1. Stay-Option Machines

simulate Standard Turing machines

2. Standard Turing machines

simulate Stay-Option machines
Costas Busch - LSU 15
1. Stay-Option Machines
simulate Standard Turing machines

Trivial: any standard Turing machine

is also a Stay-Option machine

Costas Busch - LSU 16

2. Standard Turing machines
simulate Stay-Option machines

We need to simulate the stay head option

with two head moves, one left and one right

Costas Busch - LSU 17

 Stay-Option Machine

a → b, S
q1 q2

Simulation in Standard Machine

a → b, L x → x, R
q1 q2

For every possible tape symbol x

Costas Busch - LSU 18
For other transitions nothing changes

Stay-Option Machine

a → b, L
q1 q2

Simulation in Standard Machine

a → b, L
q1 q2

Similar for Right moves

Costas Busch - LSU 19
 example of simulation

Stay-Option Machine:
q1 a → b, S q2 ◊aab a ◊ ◊b ab a ◊
1 2
q1 q2

Simulation in Standard Machine:

◊aab a ◊ ◊b ab a ◊ ◊b ab a ◊
1 2 3
q1 q2 q3

END OF PROOF
Costas Busch - LSU 20
 A useful trick: Multiple Track Tape
helps for more complicated simulations

One Tape
◊ ◊ a b a b ◊ track 1
◊ ◊ b a c d ◊ track 2

One head
One symbol ( a, b)
It is a standard Turing machine, but each tape alphabet symbol
describes a pair of actual useful symbols
Costas Busch - LSU 21
◊ ◊ a b a b ◊ track 1
◊ ◊ b a c d ◊ track 2

q1

◊ ◊ a c a b ◊ track 1
◊ ◊ b d c d ◊ track 2

q2

(b, a) → (c, d ), L
q1 q2
Costas Busch - LSU 22
 Semi-Infinite Tape
The head extends infinitely only to the right

a b a c ◊ ◊ .........

• Initial position is the leftmost cell

• When the head moves left from the border,

it returns back to leftmost position
Costas Busch - LSU 23
Theorem: Semi-Infinite machines
have the same power with
Standard Turing machines

Proof: 1. Standard Turing machines

simulate Semi-Infinite machines

2. Semi-Infinite Machines
simulate Standard Turing machines
Costas Busch - LSU 24
1. Standard Turing machines simulate
Semi-Infinite machines:
......... ◊ ◊ # a b a c ◊ ◊ .........

Standard Turing Machine

Semi-Infinite machine modifications
a. insert special symbol #
at left of input string

b. Add a self-loop #→# , R

to every state
(except states with no
outgoing transitions)
Costas Busch - LSU 25
2. Semi-Infinite tape machines simulate
Standard Turing machines:

Standard machine
......... .........

Semi-Infinite tape machine

.........

Squeeze infinity of both directions

to one direction
Costas Busch - LSU 26
 Standard machine
......... ◊ a b c d e ◊ ◊ .........

reference point

Semi-Infinite tape machine with two tracks

Right part # d e ◊ ◊ ◊ .........
Left part # c b a ◊ ◊

Costas Busch - LSU 27

 Standard machine

q2
q1

Semi-Infinite tape machine

Left part Right part
L R
q2 R q2
L
q1 q1

Costas Busch - LSU 28

 Standard machine
a → g, R
q1 q2

Semi-Infinite tape machine

R (a, x) → ( g , x), R R
Right part q1 q2

Left part L ( x, a) → ( x, g ), L L
q1 q2
For all tape symbols x
Costas Busch - LSU 29
 Time 1
Standard machine
......... ◊ a b c d e ◊ ◊ .........

q1

Semi-Infinite tape machine

Right part # d e ◊ ◊ ◊ .........
Left part # c b a ◊ ◊
L
q1
Costas Busch - LSU 30
 Time 2
Standard machine
......... ◊ g b c d e ◊ ◊ .........

q2

Semi-Infinite tape machine

Right part # d e ◊ ◊ ◊ .........
Left part # c b g ◊ ◊
L
q2
Costas Busch - LSU 31
 At the border:

Semi-Infinite tape machine

R (# , # ) → (# , # ), R L
Right part q1 q1

L (# , # ) → (# , # ), R R
Left part q1 q1

Costas Busch - LSU 32

 Semi-Infinite tape machine
Time 1
Right part # d e ◊ ◊ ◊ .........
Left part # c b g ◊ ◊
L
q1
Time 2
Right part # d e ◊ ◊ ◊ .........
Left part # c b g ◊ ◊
R
q1
END OF PROOF
Costas Busch - LSU 33
 Multi-tape Turing Machines

Control unit
(state machine)

Tape 1 Tape 2
◊ a b c ◊ ◊ e f g ◊
Input string

Input string appears on Tape 1

Costas Busch - LSU 34

Tape 1 Time 1 Tape 2
◊ a b c ◊ ◊ e f g ◊
q1 q1

Tape 1 Time 2 Tape 2

◊ a g c ◊ ◊ e d g ◊
q2 q2

(b, f ) → ( g , d ), L, R
q1 q2
Costas Busch - LSU 35
 Theorem: Multi-tape machines
have the same power with
Standard Turing machines

Proof: 1. Multi-tape machines

simulate Standard Turing machines

2. Standard Turing machines

simulate Multi-tape machines
Costas Busch - LSU 36
1. Multi-tape machines simulate
Standard Turing Machines:

Trivial: Use one tape

Costas Busch - LSU 37

2. Standard Turing machines simulate
Multi-tape machines:

Standard machine:
• Uses a multi-track tape to simulate
the multiple tapes

• A tape of the Multi-tape machine

corresponds to a pair of tracks

Costas Busch - LSU 38

 Multi-tape Machine
Tape 1 Tape 2
◊ a b c ◊ ◊ e f g h ◊

Standard machine with four track tape

a b c Tape 1
0 1 0 head position
e f g h Tape 2
0 0 1 0 head position
Costas Busch - LSU 39
Reference point
a b c Tape 1
#
# 0 1 0 head position
# e f g h Tape 2
# 0 0 1 0 head position

Repeat for each Multi-tape state transition:

1. Return to reference point
2. Find current symbol in Track 1 and update
3. Return to reference point
4. Find current symbol in Tape 2 and update
END OF PROOF
Costas Busch - LSU 40
 Same power doesn’t imply same speed:
n n
L = {a b }
2
Standard Turing machine: O ( n ) time
2
Go back and forth O ( n ) times
to match the a’s with the b’s

2-tape machine: O(n) time

n
1. Copy b to tape 2 (O(n) steps)
n
2. Compare a on tape 1
n
and b tape 2 (O(n) steps)
Costas Busch - LSU 41
 Multidimensional Turing Machines

2-dimensional tape y

◊
◊ c a x
◊ b
◊

MOVES: L,R,U,D HEAD

U: up D: down Position: +2, -1
Costas Busch - LSU 42
 Theorem: Multidimensional machines
have the same power with
Standard Turing machines

Proof: 1. Multidimensional machines

simulate Standard Turing machines

2. Standard Turing machines

simulate Multi-Dimensional machines
Costas Busch - LSU 43
1. Multidimensional machines simulate
Standard Turing machines

Trivial: Use one dimension

Costas Busch - LSU 44

2. Standard Turing machines simulate
Multidimensional machines

Standard machine:
• Use a two track tape
• Store symbols in track 1
• Store coordinates in track 2

Costas Busch - LSU 45

 2-dimensional machine
y

◊
◊ c a x
◊ b
◊

Standard Machine q1
a b c symbol
1 # 1 # 2 # − 1 # − 1 coordinates
q1 Costas Busch - LSU 46
Standard machine:

Repeat for each transition followed

in the 2-dimensional machine:
1. Update current symbol
2. Compute coordinates of next position
3. Go to new position

END OF PROOF
Costas Busch - LSU 47
Nondeterministic Turing Machines

q2 Choice 1
a → b, L

q1

a → c, R q3 Choice 2

Allows Non Deterministic Choices

Costas Busch - LSU 48

 Time 0

◊ a b c ◊
Time 1
q1
Choice 1
q2 ◊ b b c ◊
a → b, L
q2
q1
Choice 2
a → c, R q3 ◊ c b c ◊

Costas Busch - LSU

q3 49
 Input string w is accepted if
there is a computation:
∗
q0 w ≻ x q f y

Initial configuration Final Configuration

Any accept state

There is a computation:

Costas Busch - LSU 50

 Theorem: Nondeterministic machines
have the same power with
Standard Turing machines

Proof: 1. Nondeterministic machines

simulate Standard Turing machines

2. Standard Turing machines

simulate Nondeterministic machines
Costas Busch - LSU 51
1. Nondeterministic Machines simulate
Standard (deterministic) Turing Machines

Trivial: every deterministic machine

is also nondeterministic

Costas Busch - LSU 52

2. Standard (deterministic) Turing machines
simulate Nondeterministic machines:

Deterministic machine:
• Uses a 2-dimensional tape
(equivalent to standard Turing machine with one tape)

• Stores all possible computations

of the non-deterministic machine
on the 2-dimensional tape
Costas Busch - LSU 53
All possible computation paths
Initial state

Step 1

Step 2

Step i
reject accept infinite
Step i+1
path
Costas Busch - LSU 54
The Deterministic Turing machine
simulates all possible computation paths:

•simultaneously

•step-by-step

•with breadth-first search

depth-first may result getting stuck at exploring

an infinite path before discovering the accepting path
Costas Busch - LSU 55
 NonDeterministic machine

q2 Time 0
a → b, L
◊ a b c ◊
q1
q1
a → c, R q3
Deterministic machine
# # # # # #
# a b c # current
# q1 # configuration
# # # # #
Costas Busch - LSU 56
 NonDeterministic machine
Time 1
q2 ◊ b b c ◊ Choice 1
a → b, L
q2
q1
◊ c b c ◊ Choice 2
a → c, R q3 q3
Deterministic machine
# # # # # #
# b b c # Computation 1
# q2 #
# c b c #
q3 Computation 2
# #
Costas Busch - LSU 57
Deterministic Turing machine

Repeat
For each configuration in current step
of non-deterministic machine,
if there are two or more choices:
1. Replicate configuration
2. Change the state in the replicas
Until either the input string is accepted
or rejected in all configurations

Costas Busch - LSU 58

If the non-deterministic machine accepts
the input string:

The deterministic machine accepts and halts too

The simulation takes in the worst case

exponential time compared to the
shortest length of an accepting path

Costas Busch - LSU 59

If the non-deterministic machine does not
accept the input string:

1. The simulation halts if all paths

reach a halting state
OR
2. The simulation never terminates
if there is a never-ending path (infinite loop)

In either case the deterministic machine

rejects too (1. by halting or 2. by simulating the infinite loop)
END OF PROOF
Costas Busch - LSU 60