2
$\begingroup$

The wikipedia article about primitive recursion states that

An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine.

My question is how one can write down formally this definition?

$\endgroup$
  • $\begingroup$ If you are interested in the details, I suggest you get an introductory textbook on the matter. $\endgroup$ – Raphael May 16 '13 at 6:02
  • $\begingroup$ This answer is relevant. $\endgroup$ – Mars Feb 3 '18 at 18:56
2
$\begingroup$

You first define what a partial recursive function is, and then what a Turing machine is. Then you show that for every set (problem), there is a Turing machine computing it if and only if it is definable by a partial recursive function.

What you actually would do is to simulate a Turing machine by a partial recursive function and vice versa. Right to left is simple, left to right takes some work. You must define an encoding of the machine states (use of e.g. powers of prime numbers), the transition function, a configuration of a machine (i.e., what is currently on the tape, where is the head, and in which state is the machine) etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy