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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Take any non-computable 1-place function, and add a dummy argument. $\endgroup$
    – Yuval Filmus
    Oct 5, 2015 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, 2015 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, 2015 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, 2015 at 20:39
  • $\begingroup$ You already gave an example. Your statements were correct. $\endgroup$
    – Yuval Filmus
    Oct 5, 2015 at 20:45

0

Reset to default

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.