Turing Machines

Question 1

What questions does the Turing Machine bring up?

Answer 1

What does it mean to be computable?

And the limits of computability (Halting Machines)

Question 2

Approaches to formalizing computability:

Answer 2

1. Representability in a formal system (FOA)
2. Arithmetical descriptions (recursive functions)
3. Calculus
4. Machine-like descriptions

Question 3

What is the Church-Turing Thesis?

Why is it a thesis and not a theorem?

Answer 3

Why is it a thesis and not a theorem?
Not provable

Intuitive notion is the same as the formal notion

Question 4

Who was Alan Turing (1912-1954)

Answer 4

• 1936: Turing Machines
• 1939–1945 Cryptology: Deciphering the German Enigma machine.
• Almost qualified for the British 1948 Olympic Team as marathon runner
• 1950 “Computing Machinery and Intelligence”: Turing-Test for intelligence
• 1954 Apparent suicide (after conviction for homosexuality and hormone treatment)

Question 5

What was Turing’s a-machines (automatic)?

*Now called Turing Machines *

Answer 5

“On computable numbers with an applicatin to the Entscheidungsproblem (decision)”

Question 6

Turing Machines

Analysis: (2)

Answer 6

(1) Boundedness:
- Use only finite numbers of symbols and states
- Finate state and instructions (tape itself is infinite)

(2) Locality Conditions:
- Survey a finite range of reading and writing

Question 7

What do Turing Machines consist of?

Answer 7

(1) “Potentially infinite” TAPE divided into linearly ordered squares
- Blank or have a symbol from finite alphabet
- Alphabet: {B, 1}. B = Blank, and 1 = only other symbol

(2) HEAD, which is over one square at a time, and it can
(a) Read square and determine blank/1
(b) Write or delete symbol 1
(c) Move to square immediately to left or right

(3) Machine STATE (q0, q1. q2 …)
- Applies to the whole system
- Independent Action

(4) Finite State of INSTRUCTIONS given as a 4-tuple:
(q1, S, Op, qj)

Question 8

What are the instructions of the Turing Machines?

Answer 8

• q1 is the current state
• S ∃ {B, 1} symbols under the head
• Op ∃ {1, B, R, L}: Write 1, delete square, move right, move left
• qj is the next state

(q1, S, Op, qj)

Some written as a 5-tuple:

Question 9

Instructions for a Turing Machine described by 5-tuples

Answer 9

Question 10

Turing Machines

Conventions

Answer 10

1. TM always states q0 (lowest numbered state)
2. TM always states head above the leftmost non-blank state (1)
3. There is no possible instruction to follow, machine halts (terminates)
4. Program (instructions and the state) is deterministic

Question 11

What does it mean for a program to be deterministic?

Answer 11

There are no quadruples with the sme first two coordinates, but that disagree on one the last two

Question 12

What are the conventions of Turing Machines (as functions)?

Answer 12

• Interpret the input and output on the tape as numbers.
• Standard configuration of tape:
  The tape either completely blank or contains one single sequence (block) of 1 s (i. e.,
  1n ).
  [Let’s not consider zero in general, since this makes the representation unnecessarily
  complicated, without adding anything substantial.]

Alternative convention:
Hamilton (p. 172, Remark 7.22(a)) represents numbers in binary notation!

Question 13

A TM M calculates output m on input n:

Answer 13

**M* starts with a tape in standard configuration with n 1 s on the tape and with the head
on the leftmost 1 .
* M begins in q0 .
* M halts in the highest numbered state, and

1. the tape is blank: m = 0 , or
2. the tape contains one sequence of m 1 s, with the head on the leftmost element

Question 14

When is a TM computable?

Answer 14

If there is a TM that calculates it

Question 15

How many computable functions exists?

Answer 15

ℵ0

Finite instructions and finite parameters

Question 16

How many functions from ℕ to ℕ exist?

Answer 16

ℝ

Uncountable: Diagonalization

Therefore, functions that are not computable by anyone !

Question 17

Computable TM functions:

Answer 17

• Successor: S(x) = x + 1
• Zero: Z(x)=0
• Addition: plus(x, y) = x + y
• Multiplication
• Composition of two functions: f g