02/02/2016

Components of a Turing Machine

Tape: \(\leftarrow\) 0 0 0 0 0 0 [0] 0 0 0 0 0 0 \(\to\)

States: {A B C}

Symbols: {0 1}

Table:

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 [1] 1 1 1 1 0 0 0 0 \(\to\)

State: A

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 [1] 1 1 1 0 0 0 0 \(\to\)

State: A

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 [1] 1 1 0 0 0 0 \(\to\)

State: A

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 1 [1] 1 0 0 0 0 \(\to\)

State: A

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 1 1 [1] 0 0 0 0 \(\to\)

State: A

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 1 1 1 [0] 0 0 0 \(\to\)

State: A

Symbol: 0

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 1 1 [1] 1 0 0 0 \(\to\)

State: B

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 1 [1] 0 1 0 0 0 \(\to\)

State: C

Symbol: 1

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Running a Turing Machine Foward

Tape: \(\leftarrow\) 0 0 0 0 1 1 1 [1] 0 1 0 0 0 \(\to\)

State: HALTED

Symbol: HALTED

0 1

A

1LB

1RA

B

0LC

0LC

C

0HLT

1HLT

Construct an Addition Turing Machine

Computational Level

\(2 + 3 = 5\)

Algorithmic Level

Tape: \(\leftarrow\) 0 0 1 1 + 1 1 1 0 0 0 0 0 \(\to\)

  • Read the first number
  • Rewrite the + symbol
  • Remove the last digit of the second number
  • Go back to the begining
  • Halt

Construct an Addition Turing Machine

Tape: \(\leftarrow\) 0 0 1 1 + 1 1 1 0 0 0 0 0 \(\to\)

State: {A B C}

Symbol: {0, 1, +}

0 1 +

A

B

C

Construct an Addition Turing Machine

Tape: \(\leftarrow\) 0 0 1 1 + 1 1 1 0 0 0 0 0 \(\to\)

State: {A B C}

Symbol: {0, 1, +}

0 1 +

A

1RA

B

C

Construct an Addition Turing Machine

Tape: \(\leftarrow\) 0 0 1 1 + 1 1 1 0 0 0 0 0 \(\to\)

State: {A B C}

Symbol: {0, 1, +}

0 1 +

A

1RA

1RA

B

C

Construct an Addition Turing Machine

Tape: \(\leftarrow\) 0 0 1 1 + 1 1 1 0 0 0 0 0 \(\to\)

State: {A B C}

Symbol: {0, 1, +}

0 1 +

A

0LB

1RA

1RA

B

C

Construct an Addition Turing Machine

Tape: \(\leftarrow\) 0 0 1 1 + 1 1 1 0 0 0 0 0 \(\to\)

State: {A B C}

Symbol: {0, 1, +}

0 1 +

A

0LB

1RA

1RA

B

0HLT

C

What rule is needed to make this halt?

Tape: \(\leftarrow\) 0 0 0 [1] 1 1 \(\to\)

State: A

Symbol: 1

0 1

A

1LB

1RA

B

1LC

1LB

C

1HLT

Not just ones and zeros

Tape: \(\leftarrow\) [d] r e a m \(\to\)

State: word

Symbol: d

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d [r] e a m \(\to\)

State: word

Symbol: r

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d r [e] a m \(\to\)

State: word

Symbol: e

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d r e [a] m \(\to\)

State: word

Symbol: a

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d r e a [m] \(\to\)

State: word

Symbol: m

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d r e a m [ ] \(\to\)

State: word

Symbol: { }

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d r e a m e [] \(\to\)

State: suffix

Symbol: { }

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT

Not just ones and zeros

Tape: \(\leftarrow\) d r e a m e [d] \(\to\)

State: HALT

Symbol: HALT

{abc..z} { }

word

{abc..z} R word

e R suffix

suffix

d HALT