Topic 6: Turing thesis. Communication recursive functions with Turing machines
A. Turing proposed a hypothesis that is formulated as follows: grades calculated and calculated by Turing functions coincide. Bring Turing thesis as the thesis of Church, it is impossible because the very notion of an algorithm (or an effective procedure) is inaccurate. This is not a theorem and postulate a mathematical theory, and a statement that links the theory of those objects for the description of which it was created. According to its value Turing thesis resembles the hypothesis of Physics adequacy of mathematical models of physical phenomena and processes. Proof of Turing thesis is a mathematical practice and the fact that the description of the algorithm in terms of any other known algorithmic models can be reduced to its description as a Turing machine (TM).
Turing thesis allows, on the one hand, to replace the inaccurate assertions about the existence of effective procedures (algorithms) accurate statements about the existence of T M , on the other - allegations of non-existence TM interpreted as allegations of non-existence of algorithms in general. But we should understand Turing thesis in the sense that the whole theory of algorithms can be reduced to the theory of Turing machines. For example, in complexity theory of algorithms (which is now rapidly developing and considering the relative complexity of algorithms for memory, the number of actions) results are correct within an algorithmic model may be incorrect in another model.
Church thesis (any function, calculated by some algorithm, is partially-recursive) has historically been formulated before Turing thesis. From the comparison of these two abstracts follows this statement: function calculated TM if and only if it is partially recursive. This statement about the equivalence of the two algorithmic models (as opposed to abstract) is a precise mathematical statement and requires proof.
Theorem:
Any partial-recursive function is calculated on the TM .
Plan of proof of the theorem, first proved that the simplest functions that make up the complete system is calculated, and that operators of superposition, primitive recursion and minimization of retaining the ability to resolution of.
You can also prove contrary.
Theorem:
Any function, calculated on the TM is partially recursive.
