5
$\begingroup$

My course is about computability theory, and I'm having troubles with one of the main concepts. This might be a really newb question, but I've been struggling with understanding it's significance (and I was stupid enough to not ask my teacher while in class).

Can someone give me an example in terms of something practical to why numbering computable functions is helpful?

I'm a computer science student, so maybe an example from that field might help me understand.

EDIT: Okay, so with the assumption then that the halting problem is the main reason we number computable functions.

In that case, numbering the functions should help us always prove if a function will halt or not. So, say we take the gödel numbered program $P_{2057}$, which stands for the program S(1), S(1), J(2,1,1). This represents the function x+2, over the domain of $\mathbb{N}$.

How does knowing the number 2057 help us decide if this program will halt or not?

EDIT2: I tried reading the papers that @sav linked to me, although I find them relatively difficult to understand, as I'm not that good with theoretical things yet.

Our course book is Computability, An introduction to recursive function theory by Nigel Cutland. I've found online many people praising this book for being clear and easy to understand, but for me that hasn't always been the case. The teachers explanations don't always make sense either, and sometimes it feels like the book is the teacher, not her(which is one of the big reasons I finally decided to come here for help).

Therefore, another question I have is, the book claims the numbering of functions to be of utmost importance in both the s-m-n theorem, and universal functions. After reading through those parts multiple times, I still don't understand their significance, and yet they are constantly referenced in later parts. Could someone maybe try and explain this connection in another way?

$\endgroup$
7
  • $\begingroup$ Generally, once they are numbered, you can apply a diagonal argument and show that certain things can't be done. Sorry, I can't make this any vaguer. $\endgroup$ – marty cohen May 17 '15 at 3:27
  • $\begingroup$ I was hoping for something less vague, and more specific, an illustration might make it clearer $\endgroup$ – feil May 17 '15 at 3:35
  • $\begingroup$ The specific numbering isn't significant; the critical element is simply the fact that they can be numbered. For instance, one can speak of a universal function $f$ such that $f(\langle n,x\rangle)\equiv f_n(x)$, where $\langle n,x\rangle$ is a pairing function from $\mathbb{N}^2\mapsto\mathbb{N}$. The point is that the numbering provides a canonical name for a function; this allows all of the functions used to have only integer inputs, while still allowing functions to take as input other functions. $\endgroup$ – Steven Stadnicki May 17 '15 at 5:41
  • $\begingroup$ so in other words.... if you can number a function, then it is computable? If that is the case, then I still don't see the significance in numbering these functions, as that basically is just something that you can take a step further from creating a URM-program of a function, with no added benefit. $\endgroup$ – feil May 17 '15 at 6:28
  • $\begingroup$ @feil No Some functions are not computable even though you can represent them with a number. Check out the intro Alan Turing's paper that I linked you to. He states that there are some number that are definable but not computable. Those are programs that don't halt. $\endgroup$ – sav May 17 '15 at 21:51
10
$\begingroup$

You have already been numbering the computable functions, you just didn't know it at first. The first time you saw a definition of the computable functions, you saw it in the context of some specific model of computation, such as register machines. Each machine can be viewed as a "number" for the function it computes; by standard coding methods we really can represent each machine by a natural number, justifying the terminology. (For example, as soon as you can type something into a text file, you can view the file as a sequence of 0s and 1s. Prepending a 1 gives a single number representing the data you typed).

So a number is nothing more or less than a program for computing a function. Rather than viewing the program as a sequence of complex symbols, we can view it as a sequence of 0s and 1s, as a number. Of course, to make use of the program, you have to know what model of computation it was written in.

There are many different models of computation: register machines, Turing machines, WHILE programs, $\lambda$ calculus, $\mu$-recursive functions, etc. Each of these, when fully specified, gives a different numbering of the set of computable functions.

A key point in computability theory, which is not always obvious in a first course, is that the main focus is not on any of these specific models of computation - the focus is on the computable functions themselves.

So, rather than attaching ourselves to any specific model of computation, we just assume that we have a reasonable numbering of the computable functions, and work with that numbering abstractly. "Reasonable" here means that the numbering has properties stated by the s-m-n theorem, the recursion theorem, and the universal function theorem.

So, when you ask Why is numbering the computable functions helpful?, I would respond that they are already numbered! Why focus on "numbers" abstractly? We could just as well call the numbers "programs", and call the numbering a "programming system". Nothing new would come from that terminology change.

It is true that, if we have a numbering of the computable functions, knowing that some function has number 2234 instead of 2332 doesn't really mean much. The somewhat surprising thing is that the same is true in all the standard numbering systems. The undecidability of the halting problem shows, for example, that just knowing a particular register machine to compute a function is not sufficient, in general, to let you determine whether the function halts on given inputs.

In computer science, they would call this a "static analysis" of the program. The undecidability of the halting problem shows that static analysis has significant theoretical limitations. But this is true in every reasonable programming system, and we know that because the theorem about the halting problem is proved abstractly starting with an abstract numbering of the computable functions. We can prove it once and for all, rather than proving it separately for every model of computation.

$\endgroup$
2
  • $\begingroup$ The best answer so far, upvoting for that. I will have to keep looking though, since I'm not fully satisfied myself yet. Since I feel like it's so silly to come up with this kind of a numbering system if it's not used for anything. $\endgroup$ – feil May 17 '15 at 13:12
  • $\begingroup$ after talking with my teacher, and reviewing this, it seems you had a correct answer from the beginning, just me not fully understanding it. Thanks also to @sav for the links to the turing & gödel papers $\endgroup$ – feil May 20 '15 at 0:59
1
$\begingroup$

I should point you to Alan Turing's paper

In the above paper, Alan Turing shows how to design a general purpose computer. (Historical note: During world war 2, Turing built computers that would break enigma.) But those computers could only do that one thing. They were not general purpose.

Turing designs a machine that is computationally universal.

He also shows that any instruction that this machine performs can be enumerated by a number.

'Programs' are actually numbers that represent instructions that the Turing machine performs. A general purpose machine can read in any valid program and run it.

Can someone give me an example in terms of something practical to why numbering computable functions is helpful

If you are a programmer, you may have compiled a program (maybe written in C or java). This process takes instructions written in a high level language (eg C++) and converts it into a bunch of ones and zeros (ie: a binary number).

How does knowing the number 2057 help us decide if this program will halt or not?

There actually is no general way to determine if a program will halt. There are many programs that can be proved to halt, but not in general. Some programs could just loop forever.

See these videos

Part 1

Part 2

There are programming languages that only deal with a subset of programs that halt. This allows you to prove that a program will halt. The penalty for doing this is that the language is NOT Turing complete. I believe epigram is an example of this.

$\endgroup$
5
  • $\begingroup$ so the gödel numbering of functions or programs is a way to let the machine know in the machine language which function we want to use? $\endgroup$ – feil May 17 '15 at 9:26
  • $\begingroup$ Say for arguments sake that we have 2 different test cases. Let's use the same number I used earlier, 2057. Let's now have 2 different input cases, say x=0 and x=1. How does this affect the given numbering? $\endgroup$ – feil May 17 '15 at 9:40
  • $\begingroup$ To your first question: Yes. Of course a modern compiler uses a more complex encoding but that's the basic idea. Take some instructions and represent them with a number. $\endgroup$ – sav May 17 '15 at 21:49
  • $\begingroup$ Also I should add, probably the easiest way to attempt to see if a program halts is to run it. If it halts then you know it halts. If it does not halt, maybe if you just wait a bit longer it will halt .... or maybe not ... you may never know. $\endgroup$ – sav May 17 '15 at 21:54
  • $\begingroup$ en.wikipedia.org/wiki/Description_number $\endgroup$ – sav May 18 '15 at 9:48
0
$\begingroup$

You should ask your teacher during office hours. This is a concept that can be important or not, depending on what interests you and what will be on the test. It is often used to prove the halting problem cannot be solved. Having proved that, you can prove many other problems cannot be solved. The proof only shows that some instances of the halting problem cannot be solved. It could still be that all the instances you care about can be solved.

$\endgroup$
4
  • $\begingroup$ So, the only reason we number computable functions is to prove they are not decidable? $\endgroup$ – feil May 17 '15 at 3:33
  • $\begingroup$ Oh, and I couldn't care less about what will be on the test. Me passing this course or not is not important. What I find is important is what I learn here $\endgroup$ – feil May 17 '15 at 3:36
  • $\begingroup$ I am not aware of another reason, but I am not in the field. I have seen proofs that depend on the numbering to show they are not decidable, using a diagonal argument. $\endgroup$ – Ross Millikan May 17 '15 at 3:36
  • $\begingroup$ Doesn't satisfy me yet, but thanks for the effort though. $\endgroup$ – feil May 17 '15 at 3:39
-1
$\begingroup$

The numbering is just a means to an end, and is significant only in the context of the proof in which it is used.

Consider an analogous example. Suppose we have 3 pigeons and 2 pigeon-holes. If each hole can hold only 1 pigeon, prove that there will always be at least 1 pigeon not in a hole. One answer: number the pigeons 1,2,3 by the order in which they enter a hole (exclude simultaneous entry for simplicity). Then by the time pigeon 2 enters, no holes are left for pigeon 3.

Numbering the pigeons just helps with this proof, with no claim to significance of the numbering outside the proof. Numbering the computable functions is similar.

$\endgroup$

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.