xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学证明代写-HPS391

时间：2021-04-03

Activity 9: An Introduction to Turing Machines

HPS391 Rebels who Count: History of Mathematics Since 1700

MAT391 History of Mathematics since 1700

Winter 2021, Instructor: Sylvia Nickerson

Maximum points: 38/38

1 Introduction to Turing Machines

During the International Congress of Mathematicians in Paris in 1900 David

Hilbert (1862–1943), one of the leading mathematicians of the last century,

proposed a list of problems for the following generations to ponder. On the

list was whether the axioms of arithmetic are consistent, a question which

would have profound consequences for the foundations of mathematics. Con-

tinuing in this direction, in 1928 Hilbert proposed the decision problem (das

Entscheidungsproblem), which asked whether there was a standard proce-

dure that can be applied to decide whether a given mathematical state-

ment is true. In a revolutionary paper “On Computable Numbers, with an

Application to the Entscheidungsproblem” published in 1936, Alan Turing

(1912–1954) proved that the decision problem had no solution, and in doing

so he outlined the rudimentary ideas which form the basis for the mod-

ern programmable computer. Today his construction is known as a Turing

machine.

The goal of this project is to read a few excerpts from Turing’s original

paper1 and understand how to read and write simple instructions for a

Turing Machine. After carefully reading the attached pages, answer the

following:

(Task 1) Describe the workings of a Turing machine (referred to as a “com-

puting machine” in the original paper). [5 points]

(Task 2) What is the precise output of the machine in Example 1. In

your answer draw the output on the tape, as well as the binary decimal

1Turing, A.M., “On Computable Numbers with an Application to the Entschei-

dungsproblem,” Proceedings of the London Mathematical Society, 42 (1936), pp. 230–265.

1

represented and its precise real number equivalent. [6 points]

(Task 3) Design a Turing machine which generates the following output.

Be sure to justify your answer. [6 points]

010010100101001 . . .

(Task 4) Describe the behavior of the following machine, which begins with

a blank tape, with the machine in configuration α. [4 points]

Configuration Behavior

m-config. symbol operation final m-config.

α none R P1 β

α 1 R P0 β

α 0 HALT (none)

β 1 R P1 α

β 0 R P0 α

ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO

THE ENTSCHEIDUNGSPROBLEM

By A. M. Turing.

1. Computing Machines.

We have said that the computable numbers are those whose decimals are

calculable by finite means. This requires more explicit definition. No real at-

tempt will be made to justify the definitions given until we reach §9. For present

I shall only say that the justification lies in the fact that the human memory is

necessarily limited.

We may compare a man in the process of computing a real number to a

machine which is only capable of a finite number of conditions q1, q2, . . ., qR,

which will be called the “m-configurations”. The machine is supplied with a

“tape” (the analogue of paper) running through it, and divided into sections

(called “squares”) each capable of bearing a “symbol”. At any moment there

is just one square, say the r-th, bearing the symbol S(r) which is “in the

machine”. We may call this square the “scanned square”. The symbol on the

scanned square may be called the “scanned symbol”. The “scanned symbol” is

the only one of which the machine is, so to speak, “directly aware”. However,

by altering its m-configuration the machine can effectively remember some of

the symbols it has “seen” (scanned) previously. The possible behaviour of

the machine at any moment is determined by the m-configuration qn and the

2

scanned symbol S(r). This pair qn, S(r) will be called the “configuration”;

thus the configuration determines the possible behaviour of the machine. In

some of the configurations in which the scanned square is blank (i.e. bears no

symbol) the machine writes down a new symbol on the scanned square; in other

configurations it erases the scanned symbol. The machine may also change the

square which is being scanned, but only by shifting it one place to right or left.

In addition to any of these operations the m-configuration may be changed.

Some of the symbols written down will form the sequence of figures which is

the decimal of the real number which is being computed. The others are just

rough notes to “assist the memory”. It will only be these rough notes which

will be liable to erasure.

It my contention that these operations include all those which are used in

the computation of a number. The defense of this contention will be easier

when the theory of the machines is familiar to the reader. In the next section

I therefore proceed with the development of the theory and assume that it is

understood what is meant by “machine”, “tape”, “scanned”, etc.

2. Definitions.

Automatic machines.

If at each stage the motion of a machine (in the sense of §1)is completely

determined by the configuration, we shall call the machine an “automatic ma-

chine” (or a-machine).

For some purposes we might use machines (choice machines or c-machines)

whose motion is only partially determined by the configuration (hence the use of

the word “possible” in §1). When such a machine reaches one of these ambigu-

ous configurations, it cannot go on until some arbitrary choice has been made

by an external operator. This would be the case if we were using machines to

deal with axiomatic systems. In this paper I deal only with automatic machines,

and will therefore often omit the prefix a-.

Computing machines.

If an a-machine prints two kinds of symbols, of which the first kind (called

figures) consists entirely of 0 and 1 (the others being called symbols of the

second kind), then the machine will be called a computing machine. If the

machine is supplied with a blank tape and set in motion, starting from the

correct initial m-configuration the subsequence of the symbols printed by it

which are of the first kind will be called the sequence computed by the machine.

The real number whose expression as a binary decimal is obtained by prefacing

this sequence by a decimal point is called the number printed by the machine.

At any stage of the motion of the machine, the number of the scanned

3

square, the complete sequence of all symbols on the tape, and them-configuration

will be said to describe the complete configuration at that stage. The changes

of the machine and tape between successive complete configurations will be

called the moves of the machine.

3. Examples of computing machines.

I. A machine can be constructed to compute the sequence 010101 . . .. The

machine is to have the four m-configurations “b”, “c”, “f”, “e” and is capable

of printing “0” and “1”. The behaviour of the machine is described in the

following table in which “R” means “the machine moves so that it scans the

square immediately on the right of the one it was scanning previously”. Similarly

for “L”. “E” means “the scanned symbol is erased and “P” stands for “prints”.

This table (and all succeeding tables of the same kind) is to be understood to

mean that for a configuration described in the first two columns the operations

in the third column are carried out successively, and the machine then goes

over into the m-configuration described in the last column. When the second

column is blank, it is understood that the behaviour of the third and fourth

columns applies for any symbol and for no symbol. The machine starts in the

m-configuration b with a blank tape. (Example 1).

Configuration Behaviour

m-config. symbol operation final m-config.

b none P0, R c

c none R e

e none P1, R f

f none R b

If (contrary to the description §1) we allow the letters L, R to appear more

than once in the operations column we can simplify the table considerably.

Configuration Behaviour

m-config. symbol operation final m-config.

b none P0 b

b 0 R, R, P1 b

b 1 R, R, P0 b

2 Turing Machines: Induction and Recursion

The logic behind the modern programmable computer owes much to Turing’s

“computing machines,” discussed in the first section. Since the state of the

4

machine, or m-configuration as called by Turing, can be altered according

to the symbol being scanned, the operation of the machine can be changed

depending on what symbols have been written on the tape, and affords

the machine a degree of programmability. The program consists of the list

of configurations of the machine and its behavior for each configuration.

Turing’s description of his machine, however, did not include memory in

its modern usage for computers, and symbols read on the tape could not

be stored in any separate devise. Using a brilliant design feature for the

tape, Turing achieves a limited type of memory for the machine, which

allows it to compute many arithmetic operations. The numbers needed for

a calculation are printed on every other square of the tape, while the squares

between these are used as “rough notes to ‘assist the memory.’ It will only

be these rough notes which will be liable to erasure” [1, p. 232].

Turing continues: The convention of writing the figures only on alternate

squares is very useful: I shall always make use of it. I shall call the one se-

quence of alternate squares F -squares, and the other sequence E-squares. The

symbols on E-squares will be liable to erasure. The symbols on F -squares form

a continuous sequence. . . . There is no need to have more than one E-square

between each pair of F -squares: an apparent need of more E-squares can be

satisfied by having a sufficiently rich variety of symbols capable of being printed

on E-squares [1, p. 235].

Let’s examine the Englishman’s use of these two types of squares. De-

termine the output of the following Turing machine, which begins with the

tape

X . . .

and the scanner at the far left, reading the symbol X.

Configuration Behavior

m-config. symbol operation final m-config.

a X R a

a 1 R, R a

a blank P(1), R, R, P(1), R, R, P(0) b

b X E, R c

b other L b

c 0 R, P(X), R a

c 1 R, P(X), R d

d 0 R, R e

d other R, R d

e blank P(1) b

e other R, R e

5

Recall the meaning of the following symbols used for operations.

• R: Move one position to the right.

• L: Move one position to the left.

• E: Erase the currently scanned square

• P( ): Print whatever is in parentheses in the current square.

(Task 5) What is the precise output of the machine as it just finishes

configuration a and enters configuration b for the first time? Justify your

answer. [4 points]

(Task 6) What is the precise output of the machine as it just finishes

configuration a and enters configuration b for the second time? Justify your

answer. [4 points]

(Task 7) What is the precise output of the machine as it just finishes

configuration a and enters configuration b for the third time? Justify your

answer. [4 points]

(Task 8) Guess what the output of the machine is as it just finishes con-

figuration a and enters configuration b for the n-th time. Use induction to

prove that your guess is correct. Be sure to carefully write the details of this

proof by induction. [5 points]

Imagine a Turing machine, which when given two arbitrary natural numbers,

n and m, will compute the product n ·m. Suppose that the machine begins

with the tape

A 1 1 . . . 1 1 B 1 1 . . . 1 1 C

where the number of ones between A and B is n, the number of ones between

B and C is m, and the machine begins scanning the tape at the far left,

reading the symbol A. The output of the machine should be:

A 1 . . . 1 B 1 . . . 1 C 1 1 . . . 1 D

where the number of ones between C and D is n ·m.

If T denotes the Turing machine which multiplies n and m together, so

that the value of T (n, m) is n ·m, then for n ∈ N,

T (n, 1) = n

and for m ∈ N, m ≥ 2, we have

T (n, m) = T (n, m− 1) + n.

6

Such an equation provides an example of a recursively defined function, an

important topic in computer science. In this case, the algorithm for multi-

plication, T , is defined in terms of addition, a more elementary operation.

REFERENCES:

[1] Turing, A. M., “On Computable Numbers with An Application to the

Entscheidungsproblem,” Proceedings of the London Mathematical Society,

42, 1936, pp. 230–265.

7

学霸联盟

HPS391 Rebels who Count: History of Mathematics Since 1700

MAT391 History of Mathematics since 1700

Winter 2021, Instructor: Sylvia Nickerson

Maximum points: 38/38

1 Introduction to Turing Machines

During the International Congress of Mathematicians in Paris in 1900 David

Hilbert (1862–1943), one of the leading mathematicians of the last century,

proposed a list of problems for the following generations to ponder. On the

list was whether the axioms of arithmetic are consistent, a question which

would have profound consequences for the foundations of mathematics. Con-

tinuing in this direction, in 1928 Hilbert proposed the decision problem (das

Entscheidungsproblem), which asked whether there was a standard proce-

dure that can be applied to decide whether a given mathematical state-

ment is true. In a revolutionary paper “On Computable Numbers, with an

Application to the Entscheidungsproblem” published in 1936, Alan Turing

(1912–1954) proved that the decision problem had no solution, and in doing

so he outlined the rudimentary ideas which form the basis for the mod-

ern programmable computer. Today his construction is known as a Turing

machine.

The goal of this project is to read a few excerpts from Turing’s original

paper1 and understand how to read and write simple instructions for a

Turing Machine. After carefully reading the attached pages, answer the

following:

(Task 1) Describe the workings of a Turing machine (referred to as a “com-

puting machine” in the original paper). [5 points]

(Task 2) What is the precise output of the machine in Example 1. In

your answer draw the output on the tape, as well as the binary decimal

1Turing, A.M., “On Computable Numbers with an Application to the Entschei-

dungsproblem,” Proceedings of the London Mathematical Society, 42 (1936), pp. 230–265.

1

represented and its precise real number equivalent. [6 points]

(Task 3) Design a Turing machine which generates the following output.

Be sure to justify your answer. [6 points]

010010100101001 . . .

(Task 4) Describe the behavior of the following machine, which begins with

a blank tape, with the machine in configuration α. [4 points]

Configuration Behavior

m-config. symbol operation final m-config.

α none R P1 β

α 1 R P0 β

α 0 HALT (none)

β 1 R P1 α

β 0 R P0 α

ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO

THE ENTSCHEIDUNGSPROBLEM

By A. M. Turing.

1. Computing Machines.

We have said that the computable numbers are those whose decimals are

calculable by finite means. This requires more explicit definition. No real at-

tempt will be made to justify the definitions given until we reach §9. For present

I shall only say that the justification lies in the fact that the human memory is

necessarily limited.

We may compare a man in the process of computing a real number to a

machine which is only capable of a finite number of conditions q1, q2, . . ., qR,

which will be called the “m-configurations”. The machine is supplied with a

“tape” (the analogue of paper) running through it, and divided into sections

(called “squares”) each capable of bearing a “symbol”. At any moment there

is just one square, say the r-th, bearing the symbol S(r) which is “in the

machine”. We may call this square the “scanned square”. The symbol on the

scanned square may be called the “scanned symbol”. The “scanned symbol” is

the only one of which the machine is, so to speak, “directly aware”. However,

by altering its m-configuration the machine can effectively remember some of

the symbols it has “seen” (scanned) previously. The possible behaviour of

the machine at any moment is determined by the m-configuration qn and the

2

scanned symbol S(r). This pair qn, S(r) will be called the “configuration”;

thus the configuration determines the possible behaviour of the machine. In

some of the configurations in which the scanned square is blank (i.e. bears no

symbol) the machine writes down a new symbol on the scanned square; in other

configurations it erases the scanned symbol. The machine may also change the

square which is being scanned, but only by shifting it one place to right or left.

In addition to any of these operations the m-configuration may be changed.

Some of the symbols written down will form the sequence of figures which is

the decimal of the real number which is being computed. The others are just

rough notes to “assist the memory”. It will only be these rough notes which

will be liable to erasure.

It my contention that these operations include all those which are used in

the computation of a number. The defense of this contention will be easier

when the theory of the machines is familiar to the reader. In the next section

I therefore proceed with the development of the theory and assume that it is

understood what is meant by “machine”, “tape”, “scanned”, etc.

2. Definitions.

Automatic machines.

If at each stage the motion of a machine (in the sense of §1)is completely

determined by the configuration, we shall call the machine an “automatic ma-

chine” (or a-machine).

For some purposes we might use machines (choice machines or c-machines)

whose motion is only partially determined by the configuration (hence the use of

the word “possible” in §1). When such a machine reaches one of these ambigu-

ous configurations, it cannot go on until some arbitrary choice has been made

by an external operator. This would be the case if we were using machines to

deal with axiomatic systems. In this paper I deal only with automatic machines,

and will therefore often omit the prefix a-.

Computing machines.

If an a-machine prints two kinds of symbols, of which the first kind (called

figures) consists entirely of 0 and 1 (the others being called symbols of the

second kind), then the machine will be called a computing machine. If the

machine is supplied with a blank tape and set in motion, starting from the

correct initial m-configuration the subsequence of the symbols printed by it

which are of the first kind will be called the sequence computed by the machine.

The real number whose expression as a binary decimal is obtained by prefacing

this sequence by a decimal point is called the number printed by the machine.

At any stage of the motion of the machine, the number of the scanned

3

square, the complete sequence of all symbols on the tape, and them-configuration

will be said to describe the complete configuration at that stage. The changes

of the machine and tape between successive complete configurations will be

called the moves of the machine.

3. Examples of computing machines.

I. A machine can be constructed to compute the sequence 010101 . . .. The

machine is to have the four m-configurations “b”, “c”, “f”, “e” and is capable

of printing “0” and “1”. The behaviour of the machine is described in the

following table in which “R” means “the machine moves so that it scans the

square immediately on the right of the one it was scanning previously”. Similarly

for “L”. “E” means “the scanned symbol is erased and “P” stands for “prints”.

This table (and all succeeding tables of the same kind) is to be understood to

mean that for a configuration described in the first two columns the operations

in the third column are carried out successively, and the machine then goes

over into the m-configuration described in the last column. When the second

column is blank, it is understood that the behaviour of the third and fourth

columns applies for any symbol and for no symbol. The machine starts in the

m-configuration b with a blank tape. (Example 1).

Configuration Behaviour

m-config. symbol operation final m-config.

b none P0, R c

c none R e

e none P1, R f

f none R b

If (contrary to the description §1) we allow the letters L, R to appear more

than once in the operations column we can simplify the table considerably.

Configuration Behaviour

m-config. symbol operation final m-config.

b none P0 b

b 0 R, R, P1 b

b 1 R, R, P0 b

2 Turing Machines: Induction and Recursion

The logic behind the modern programmable computer owes much to Turing’s

“computing machines,” discussed in the first section. Since the state of the

4

machine, or m-configuration as called by Turing, can be altered according

to the symbol being scanned, the operation of the machine can be changed

depending on what symbols have been written on the tape, and affords

the machine a degree of programmability. The program consists of the list

of configurations of the machine and its behavior for each configuration.

Turing’s description of his machine, however, did not include memory in

its modern usage for computers, and symbols read on the tape could not

be stored in any separate devise. Using a brilliant design feature for the

tape, Turing achieves a limited type of memory for the machine, which

allows it to compute many arithmetic operations. The numbers needed for

a calculation are printed on every other square of the tape, while the squares

between these are used as “rough notes to ‘assist the memory.’ It will only

be these rough notes which will be liable to erasure” [1, p. 232].

Turing continues: The convention of writing the figures only on alternate

squares is very useful: I shall always make use of it. I shall call the one se-

quence of alternate squares F -squares, and the other sequence E-squares. The

symbols on E-squares will be liable to erasure. The symbols on F -squares form

a continuous sequence. . . . There is no need to have more than one E-square

between each pair of F -squares: an apparent need of more E-squares can be

satisfied by having a sufficiently rich variety of symbols capable of being printed

on E-squares [1, p. 235].

Let’s examine the Englishman’s use of these two types of squares. De-

termine the output of the following Turing machine, which begins with the

tape

X . . .

and the scanner at the far left, reading the symbol X.

Configuration Behavior

m-config. symbol operation final m-config.

a X R a

a 1 R, R a

a blank P(1), R, R, P(1), R, R, P(0) b

b X E, R c

b other L b

c 0 R, P(X), R a

c 1 R, P(X), R d

d 0 R, R e

d other R, R d

e blank P(1) b

e other R, R e

5

Recall the meaning of the following symbols used for operations.

• R: Move one position to the right.

• L: Move one position to the left.

• E: Erase the currently scanned square

• P( ): Print whatever is in parentheses in the current square.

(Task 5) What is the precise output of the machine as it just finishes

configuration a and enters configuration b for the first time? Justify your

answer. [4 points]

(Task 6) What is the precise output of the machine as it just finishes

configuration a and enters configuration b for the second time? Justify your

answer. [4 points]

(Task 7) What is the precise output of the machine as it just finishes

configuration a and enters configuration b for the third time? Justify your

answer. [4 points]

(Task 8) Guess what the output of the machine is as it just finishes con-

figuration a and enters configuration b for the n-th time. Use induction to

prove that your guess is correct. Be sure to carefully write the details of this

proof by induction. [5 points]

Imagine a Turing machine, which when given two arbitrary natural numbers,

n and m, will compute the product n ·m. Suppose that the machine begins

with the tape

A 1 1 . . . 1 1 B 1 1 . . . 1 1 C

where the number of ones between A and B is n, the number of ones between

B and C is m, and the machine begins scanning the tape at the far left,

reading the symbol A. The output of the machine should be:

A 1 . . . 1 B 1 . . . 1 C 1 1 . . . 1 D

where the number of ones between C and D is n ·m.

If T denotes the Turing machine which multiplies n and m together, so

that the value of T (n, m) is n ·m, then for n ∈ N,

T (n, 1) = n

and for m ∈ N, m ≥ 2, we have

T (n, m) = T (n, m− 1) + n.

6

Such an equation provides an example of a recursively defined function, an

important topic in computer science. In this case, the algorithm for multi-

plication, T , is defined in terms of addition, a more elementary operation.

REFERENCES:

[1] Turing, A. M., “On Computable Numbers with An Application to the

Entscheidungsproblem,” Proceedings of the London Mathematical Society,

42, 1936, pp. 230–265.

7

学霸联盟