I'm reading Computation Complexity: A Modern Approach and one of the exercises is:

Prove that [the addition function is] computable by writing down a full description (including the states, alphabet, and transition function) of the corresponding Turing [machine].

I successfully wrote this description but I don't think it is a proof the addition function is computable.

According to this question, the definition of a computable function is:

If $f:\Sigma^* \to \Sigma^*$ is function, and $\exists$ a Turing machine which on the input $w\in\Sigma^*$ writes $f(w)$, $\forall w\in\Sigma^*$, then we call $f$ as computable function.

With the Turing machine I wrote, I can prove the machine is able to compute $f(w)$ for some inputs but how can I prove it can do the same for every inputs $w\in\Sigma^*$? In other words, how can I prove $f$ is computable?

  • $\begingroup$ I just want to precise I'm totally new in this field of mathematics. If you think I have some gaps with basics notions, don't hesitate to provide resources I can use to learn. Thanks. $\endgroup$ – Pierre Nov 11 '20 at 16:50

If you can prove that for any two integers $m,n$ the output of your machine is $m+n$, you are done.

You are in a situation like this one: prove a theorem. If you find a proof, obviously your proof may be wrong and someone maybe able to correct your error.

Your Turing program may be wrong, but validating it in Mathematical logic won't go through testing it with various values... but by convincing you (and the others) that your Turing program is the right one.

Additional elements

According to Church-Turing thesis, every computable function can be computed by a Turing machine and there are ways to convert a $\mu$-recursive function into a Turing machine. Based on those methods (that you have to validate!) you can convert the addition which is primitive recursive into a Turing machine.

  • $\begingroup$ Indeed, I don't want to test all the possible inputs. But how can I convince others I'm right? Is there a formal way to show a Turing machine always compute the right output of a function? $\endgroup$ – Pierre Nov 11 '20 at 17:20
  • $\begingroup$ Naive answer would be the question how do you convince someone else that your proof of a theorem is correct? Theorical results for Turing machine may exist, but I I'm ignorant there. Maybe Automated theorem proving or proof theory articles in wikipedia are good starting point to explore the question. $\endgroup$ – mathcounterexamples.net Nov 11 '20 at 17:31
  • $\begingroup$ Some additional elements in the answer. $\endgroup$ – mathcounterexamples.net Nov 11 '20 at 18:02

You could potentially construct a Turing Machine that takes an two inputs, one of the form "m + n", and one of the form "x", where "m + n" is the two integers to be added and "x" is the sum. Make this Turing Machine reject if "m + n $\neq$ x" and accept if "m + n = x". If you can prove that this machine halts on all inputs (read: accepts or rejects) and accurately calculates all sums, then you could use this deciding TM to generate a language consisting of all pairs of numbers and their sums. Not sure if this is the approach the question asks for but this would be my approach.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.