Non Computable Functions And Godel's Theorem

  • Thread starter bhobba
  • Start date

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,337
2,510
Yes. My mistake.


The crux of my objection was here. Consider the busy beaver function, (##BB(n)## = the maximum number of steps that an ##n##-state Turing machine takes before it halts, excluding non-halting TM's) which is by definition non-computable (equivalent to the halting problem). However, given an ##n##, we can find (and have found) at least a few specific values of ##BB(n)##, for instance ##BB(4)=107##. The whole reason we can do that is because we can enumerate all 4-state Turing machines and exhaustively show that any of these TM's that runs for more than 107 steps eventually enters a loop (and therefore never halts). So even though the busy beaver function isn't computable, we can still find ##BB(n)## for specific values of ##n##.
Yes, there are certainly cases where you can prove that a program definitely does halt on certain inputs, and there are cases where you can prove that a program definitely does not halt on certain inputs. But to get a listing of all computable programs, you need to be able to tell, for an arbitrary program, whether it halts on all possible inputs.
 
164
28
baobab said:
Sure a program to sort them alphabetically will never terminate since their number is infinitely countable it is not computeable. But its irrelevant to my argument. You can put them in 1-1 correspondence with the natural numbers by the well ordering theorem.
I wasn't trying to say your original argument is invalid. Just found it interesting what else it proves. I don't think not being able to find the index of a computable function in an enumeration of them invalidates your proof. It's just an interesting related fact.
Yes. My mistake.


The crux of my objection was here. Consider the busy beaver function, (##BB(n)## = the maximum number of steps that an ##n##-state Turing machine takes before it halts, excluding non-halting TM's) which is by definition non-computable (equivalent to the halting problem). However, given an ##n##, we can find (and have found) at least a few specific values of ##BB(n)##, for instance ##BB(4)=107##. The whole reason we can do that is because we can enumerate all 4-state Turing machines and exhaustively show that any of these TM's that runs for more than 107 steps eventually enters a loop (and therefore never halts). So even though the busy beaver function isn't computable, we can still find ##BB(n)## for specific values of ##n##.
But for a single program to accompish this for the general case, you may need infinitely long source code.

But good point. It doesn't need to be the case that given ##k## you cannot find ##f_k(k)##. It's just the case that you cannot have one algorithm that can find ##f_k(k)## for all ##k##. As you iterate, you would need to (at least) keep creating new logic in order to continue your success. All in all, you need to be infinitely creative so to speak. I think.
 
Last edited:
297
36
Just to make a (relatively simple) point clearer ...... once we have set up the specifics of our programming language then indeed we can put all the (syntactically valid) programs in one-to-one correspondence with ##\mathbb{N}##. And indeed there is a computer program that can then calculate the function ##g : \mathbb{N} \rightarrow \mathbb{N}## defined as:
##g(x)=f_x(x)+1## ---- if ##f_x(x)## is defined
##g(x)=##undefined ---- if ##f_x(x)## is undefined***

Here ##f_x## corresponds to the (partial recursive) function computed by program with index ##x##. One can observe that the function ##g## is a partial recursive function but not a (total) recursive function.

The problem is of course that the 1-1 correspondence was between programs that compute partial computable functions and ℕ. The correspondence was NOT between programs computing (total) computable functions and ℕ. This is quite customary (and standard usage) that even when one says partial computable function, one is "really" talking about a function that may either be:
-- total
-- not total

I think this is slightly against the convention taken in mathematics more generally where partial function is specifically taken to mean a non-total function .. but anyway.

***When we say that a given partial computable function ##g## is undefined on a given input value (say ##a##), what we simply mean is that the program computing ##g## doesn't halt on the given input.


EDIT: Edited the post to make it clearer.
 
Last edited:

stevendaryl

Staff Emeritus
Science Advisor
Insights Author
8,337
2,510
Just to make a (relatively simple) point clearer ...... once we have set up the specifics of our programming language then indeed we can put all the (syntactically valid) programs in one-to-one correspondence with ##\mathbb{N}##. And indeed there is a computer program that can then calculate the function ##g : \mathbb{N} \rightarrow \mathbb{N}## defined as:
##g(x)=f_x(x)+1## ---- if ##f_x(x)## is defined
##g(x)=##undefined ---- if ##f_x(x)## is undefined***
With that modified definition of ##g##, it is (partial) computable. The original argument that proved that ##g(x)## can't be on the list was:

For any ##n##, ##g(x)## cannot be equal to ##f_n(x)##, because then ##g(n)## would be equal to ##f_n(n)##, while it's been defined to be: ##1 - f_n(n)##.

But that's not a contradiction if you interpret the equals sign loosely: ##g(n) = 1 - f_n(n)## means either that both sides are equal to the same number, or that both sides are undefined.
 
297
36
Yes ofc you are right. I wasn't disputing the original argument (in OP) indeed. I was just pointing out that:
1--- Even though we can't computably do (what was described in OP) for total recursive functions, we can indeed do it for partial recursive functions (but diagonalisation fails in that case of course).
2--- I was also trying to point out (somewhat implicitly) that even in that case one is only computably listing the outputs of programs and hence there is infinite repetition of a given partial recursive function on such a list.
Of course, repetition or not, this is still provably impossible to do (computably) for total computable functions (as in OP). Indeed that's simply because repetitions of a specific function on the list is irrelevant for diagonalisation to work in that case ..... it just has to be on the list at least once.
 
Last edited:

Jimster41

Gold Member
681
64
you lost me here.

Well all computer programs are countable because they use a finite number of characters and are of finite length.
Who wrote the internet? What is a computer program if not the internet? Is it done? It's like you are drawing a line across some joint of a thing and then counting the bones on one side.
 

berkeman

Mentor
54,730
5,002
you lost me here.



Who wrote the internet? What is a computer program if not the internet? Is it done? It's like you are drawing a line across some joint of a thing and then counting the bones on one side.
As @bhobba points out, you do not seem to have the technical background yet to be throwing out a philosophical question in this technical thread. Please do some reading about the technical aspects of this discussion, and then if you have pertinent questions, go ahead and post them in context. Thank you.
 

Want to reply to this thread?

"Non Computable Functions And Godel's Theorem" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top