0
$\begingroup$

I'm just refreshing my memory on Turing machines and computability, and I was wondering how to design a function of 2 arguments that is guaranteed not to be computable. I've seen the proof (by diagonalization) for one argument functions, and I'd like to make sure I have the right idea. For functions with 2 arguments, a sketch of my proof is as follows:

Let f_{1},f_{2}... be a listing of all 2 argument Turing computable functions

Let d be a 2 place function (and assume that it is Turing computable) such that d(x,y)=1 if the xth function in the list of Turing computable functions returns 0, and return 1 otherwise. Then d is not in our list of functions, but it was assumed that it was. Therefore, d is not a computable function of 2 arguments. Sorry for the lack of latex, hopefully this is understandable without it for now.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Take any non-computable 1-place function, and add a dummy argument. $\endgroup$ – Yuval Filmus Oct 5 '15 at 20:13
  • $\begingroup$ So if I'm understanding this right, extend the definition as follows. d(n,x)=1 if the nth function returns a 0, 0 otherwise? So in some sense, you can input 2 arguments, but only one matters? $\endgroup$ – user979616 Oct 5 '15 at 20:18
  • $\begingroup$ It's a "black-box" definition. You start with any 1-place non-computable function and end up with a 2-place non-computable one. $\endgroup$ – Yuval Filmus Oct 5 '15 at 20:34
  • $\begingroup$ I'm not sure I understand what you're saying. Would you mind fleshing out an example? $\endgroup$ – user979616 Oct 5 '15 at 20:39
  • $\begingroup$ You already gave an example. Your statements were correct. $\endgroup$ – Yuval Filmus Oct 5 '15 at 20:45

Your Answer

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

Browse other questions tagged or ask your own question.