Machine of Turing

1) Describe the concept of machine of Turing:

Draft of a conceptual abstraction based on the observation of as the man resolves the problems.

2) Describe the physical model of the machine of Turing:

It is constituted gives:

to) a supervisory body in which a program to execute is present and the organ executor who takes care of the movements.

b) a limitless tape having function of memory subdivided in many cases ognuna di.le which can contain a symbol, on the tape can find place a n° ended of symbols not blank and remaining infinitely of symbols blank.

3) Which operations are granted to the machine of Turing:

4 operations are granted of which all the reading testina of and writing implemented from the T.L.S. that is from:

to) reading the present symbol in the cell they of the tape puts into effect

b) To write a symbol in the cell puts into effect automatically cancelling they the symbol that previously was written you.

c) To move itself on the next cell on the left of the tape.

d) To move itself on the next right cell of the tape.

4) Like extrinsic the operation of one machine of Turing:

Through one such matrix:

Lines are all the possible states in which the m.d.T. it can be found.

Columns are all the possible symbols that the m.d.T. it can meet.

" combination of income constituted from the cartesian product be puts into effect them ^X met symbol, has in the intersection of the matrix a tern that represents the output of puts into effect them elaboration step, constituted they give:

a) symbol to replace to the read symbol.

b) new be that the machine must assume.

c) position of the next symbol to analyze.

5) Describe the algebrico model of the machine of Turing:

According to this model the m.d.T. it is not that one constituted tern gives:

to) Q ended Entirety of the states

b) S ended Entirety of the symbols

c) P Sottoset of with of the quintuple formed gives:

c, a) be puts into effect them

c, b) symbol puts into effect them

c, c) symbol to replace to the symbol puts into effect them

c, d) new be

c, e) movement to carry out in order to read the successive symbol.

6) What is the meaning for instantaneous configuration of one machine of Turing:

It is one tightens in a position to estrinsecare the condition of the machine of Turing in a data moment. Beginning from an instantaneous configuration of departure can be reached the final configuration through uses it of the matrix works them and the consequent modernization of the instantaneous configuration.

An instantaneous configuration is one tightens such: h q_I s_Kx where:

h is tightens it meaningful of tape that precedes the currently read cell

q the is the state in which currently the machine of Turing is found

s_K is the currently read symbol

x is tightens it meaningful of tape that follows the read cell attualmente.

7) What is the meaning for computazione of one machine of Turing:

It is a sequela of instantaneous descriptions that to leave from the instantaneous description door to one begins them be final.

8) Outline for the planning of an algorithm with the machine of Turing:

to) Finding the simplest configuration it begins them such that applying them the algorithm we are in a position to saying that she works.

b) To plan an algorithm that simply resolves the problem working on it tightens.

* To clearly characterize the condition of closing of the algorithm and eventual inner cycles.

c) To try the algorithm on tightens champion.

9) Enounce the thesis of Church:

If a problem admits an algorithmic resolution, then of it it admits one expressed from a machine of Turing (previa codifies of the data).

10) Exist insoluble problems:

, an example is the algorithm of the stopped one

11) Which are the characteristics of an algorithm:

a) must descrivibile with a n° be ended of instructions.

b) us does not have any to be a limit to the n° of data in income of to the n° of data in escape.

c) the instructions do not have to be ambiguous.

d) the complexity of the instructions must have an ended limit.

and) the executor must have to disposition one limitless memory in order memorizzare the data.

f) the algorithm must finish after a n° ended of steps.

12) When an algorithm is more complex than an other:

An algorithm is more complex if he is less efficient where the efficiency comes quantified taking in consideration the amount of resources (memory time of execution) that they come engaged.

13) When a problem is treatable :

When an algorithm exists that resolves it in polinomiali terms.