Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Phil 325 Logic II

Turing Machines

Components of a Turing Machine

1.  Storage. An infinite tape with countably many cells, finitely many of which contain strokes (1), and the rest blanks (0).

2.  Scanning and Writing Device. A contraption that can move left and right over the tape, scan the contents of a given cell, and write and erase strokes in that cell.

3. Instructions.  The scanning and writing device is governed by a set of instructions that take the form of a finite list of states. Each state gives conditional instructions. Depending on the contents of the cell the machine is currently scanning (i.e., 0 or 1), it specifies:

(a)  Overt action:  which of four possible operations the scanning and writing device is to per- form: write a blank (0), write a stroke (1), move left (L), or move right (R)

(b)  Covert action:  which state the machine is to move into next (i.e., what instructions the machine should follow in the next step)

The machine starts in state 1 and it stops when it runs out of instructions.

Turing Computable Functions

–  We represent any natural number n 2 N by a tape that contains a block of n consecutive strokes, and blanks everywhere else. Thus 4 is represented by . . . 000011110000. . .

– A function f  : N ! N is Turing computable if we can build a Turing machine that does the following. For any n  2 N, if we start the Turing machine on the leftmost stroke of a block of n strokes, then the Turing machine ultimately comes to a halt on the leftmost stroke of a block of f (n) strokes.

–  More generally, we represent a k-tuple〈n1 ; n2 ; : : : ; nk〉of natural numbers by a sequence of blocks of n1 , n2 , . . . , nk  strokes that are separated by one blank.  For example,〈4; 3〉is represented by . . . 000011110111000. . . . A function of k arguments

is Turing computable if we can build a Turing machine that computes all its values.