# Designing a 2 place function that is not Turing computable

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.

• Take any non-computable 1-place function, and add a dummy argument. Oct 5, 2015 at 20:13
• 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? Oct 5, 2015 at 20:18
• 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. Oct 5, 2015 at 20:34
• I'm not sure I understand what you're saying. Would you mind fleshing out an example? Oct 5, 2015 at 20:39
• You already gave an example. Your statements were correct. Oct 5, 2015 at 20:45