Halting problem for alexander

[phillip1882]

all right, here's my code that your program has to determine whether or not it will halt.

 

x = 7
prime = [2,3,5]
a = 1 , b =2
while x <prime[a]*prime[b]:
  prime = primefunc(prime,x)
  i = len(prime) -1
  if prime[i] -prime[i-1] == 2:
     a = i
     b = i -1
  x = x+2

where primefunc generates all prime numbers up to and including x.

i have no idea whether this will end. of course it should end eventually simply from computational space, but that's not a valid halt.

[Kriminal99]

Nice one.

 

So the question is basically is there ever a number that is higher than the last two primes under it multiplied by one another, yet lower than the next prime? I seriously doubt it. The only case that even makes you think it could happen would be some ridiculously high number right before the next prime, but by that point the number the two primes multiplied into would be astronomical. The primes never run out, so there is no reason to believe that there is an arbitrarily high gap between two primes.

 

I see your point though, since there is no way to be certain. If this is true, then something like this should be used to explain the argument because the halting proof has all kinds of logic errors in it.

[phillip1882]

actually its a little harder. the program is, will it ever be the case that the previous twin prime product is less than the next twin prime?

the twin prime conjecture hasn't been proven yet, let alone this modified version of it.

[phillip1882]

yeah so basically all you ever need to do if you really get someone stubbornly claiming that the halting problem is not accurate is to write a while loop that tests the condition of an unsolved problem. the twin prime is one of my favourites, but you could do the riemann hypothesis as well.

[Pyrotex]

Hi, guys.

I'm sorry to interrupt, but it may be possible that you have overlooked something.

 

According to Wikipedia, "...the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.

 

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines."

 

So, if you choose one particular algorithm, say finding the next prime number, and use that alone -- you have NOT proven that the halting problem is bogus, or that Turing was wrong, or that the whole thing is "full of errors".

 

What Turing asked was, (1) Is there an Algorithm, A(i,x), that has two inputs;

 

(2) The first input, i, is a description (or the code itself) of any arbitrary program;

 

(3) The second input is a finite value, x;

 

(4) Can the algorithm A(i,x) decide whether or not the program, i, will halt or not, if you feed the input, x, into the program, i?

 

Turing proved that the existence of such an Algorithm, A(i,x), capable of doing this for ANY ARBITRARY PROGRAM, i, AND ARBITRARY VALUE, x, was impossible.

[alexander]

I think he was referring to recursive functions, Turning that is, which is the one case in which it is actually extremely hard or probably impossible to predict a a halt, or lack thereof, any non-recursive case though, such as the one above, we can create an algorithm to predict whether or not the above program will halt or not... i will start on it when i get home, maybe a few hours...

[phillip1882]

alexander, i mean no offence, but i honestly don't see how you can write such a program. even if your program ran thorugh the loop say 1,000 times and saw that x is < pime[a]*prime for each x value, this doesn't mean my while loop will never end. it could predict that it won't end, but how would you show that;s the correct result?

[CraigD]

I think he was referring to recursive functions, Turning that is, which is the one case in which it is actually extremely hard or probably impossible to predict a a halt, or lack thereof …

No, Turning’s 1936 proof of the impossibility undecidability of the halting problem (you can actually read it, if you follow the references from the preceeding link, but I recommend secondary source descriptions of it, like this one given in an older thread) does not apply to any single class of computer programs, but to any purely deterministic program.

 

Put shortly, Turning’s proof is not a proof that any halting problem particular program to decide if any other particular program halts can’t work, or that some halting problem program halts can’t work if applied to itself – it’s a description of how, given any halting problem program, you can construct a program it can’t succeed in deciding.

 

Because the requirement of the halting problem is a program that works on any program, showing that for any program, there is at least one program on which it doesn’t work, proves that no such single program exists.

… any non-recursive case though, such as the one above, we can create an algorithm to predict whether or not the above program will halt or not... i will start on it when i get home, maybe a few hours...

You can certainly have fun trying (and for a restricted collection of programs to be checked, succeed), and be the better for it! :)

 

A point off the subject of the halting problem: for any program written using recursion, it’s trivial to write a program not using recursion that will function exactly the same. Most people are satisfied that this is true without proof or example (well, an example is satisfying, and left as an exercise to the reader) by considering that all computer programs that have been run on ordinary computers, regardless of the language in which their source code is written, are translated into machine language opcodes, and that ordinary CPUs don’t have any recursive opcodes. The executable code of a program written using recursion has been translated by its compiler or interpreter into one that does not use recursion.

[Pyrotex]

Using algorithm A(i,x) as the program fed into A(i,x) doesn't make any difference.

 

All you have then is A(A(i,x),x). The external 'A' is the working algorithm. The internal 'A' is just a code listing, if you will. It's just a piece of data, a string of ASCII, a string of 0s and 1s. And the x is just a constant that will appear only twice: once as input to the algorithm, and once on the code listing where the value of x replaces the symbol x.

 

No recursion takes place. The external 'A' algorithm never even knows that it is 'eating' a code listing for itself. It makes no difference.

[phillip1882]

i must admit, i've never fully understood alan turing's proof.

i understand why its true, but the proof itself seems strange.

here's what the proof seems to be saying...

imagine i have an algorithm that can finitely, deterministically, determine whether or not any algorithm i, on any input x, will halt.

take this halting algorithm, create a new algorithm out of it that's modified slightly. if the halting algorithm returns halt, loop indefinitely, if it returns not halt, return halt.

what will the original halting algorithm, when run on the modified version, return?

since it loops indefinitely whenever the original program halts, and halts whenever the original program doesn't, we have a contradiction.

 

here's my difficulty understanding to proof.

if my original algorithm can finitely deterministically determine whether or not any algorithm halts, why would it have any difficulty on this modified program? that is, why is this a contradiction?

[CraigD]

here's what the proof seems to be saying...

imagine i have an algorithm that can finitely, deterministically, determine whether or not any algorithm i, on any input x, will halt.

…

Your description sounds right to me.

here's my difficulty understanding to proof.

if my original algorithm can finitely deterministically determine whether or not any algorithm halts, why would it have any difficulty on this modified program? that is, why is this a contradiction?

Because the imagined halting problem deciding algorithm doesn’t exist.

 

This is how essentially all RAA proofs work: you assume a proposition true – in this case, that a halting problem solving algorithm exists – then prove that this assumption results in a contradiction.

 

Simpler, more well-know RAA proofs, such as these proofs that [math]\sqrt{2}[/math] is irrational, are easier to fully understand, because, I think, their underlying operations, ordinary arithmetic, are more intuitively understandable than the general “execution of an algorithm/running of a program” operations of Turing’s halting problem undecidability proof.

[phillip1882]

let me try to explain my problem better.

let's assume (i,x) is a random, non halt detection algorithm, H(i,x) is a working halt detection algorithm, and H' is the modified halt algorithm.

what turing seems to be saying is H(H'(H(i,x))) necessaryly leads to a contradiction. i would argue against this however. H would work just as well on H' if its truly universal, as it would on another algorithm.

it not that i believe a universal halt detection algorithm can be written, i know one can't, but that the contradiction for the initial assumtion isn't really there as far as i can tell.

[alexander]

i am still trying to decide how i should approach this, but i think i'll just start and we'll modify the pseudo-code as we go along... (off to type it all up)

[phillip1882]

alexander, let's assume for the sake of argument that you write an algorithm that successfully determines whether or not my first program will halt.

here's algorithm #2 that it has to evaluate.

while:
 if world hasn't ended:
    pass
 else:
    break

will this loop ever end?

:(

[phillip1882]

the halting problem to me would be like stating the following:

assumption: i can prove anything to be true, even things which have been proven false.

(need 2 +2 to equal 5? redefine what "2" stands for or what "+" stands for, etc.)

to prove this is not the case, take a known false problem, give it to me, and see how it evaluates. if evalautes to true, this contradicts the known falsehood, if false, this contradicts assumption.

while the second part is true, the first part is not. i don't know the problem is false, and you would have to prove the problem is false to me, who can prove anything true.

[Pyrotex]

phillip,

you know, sometimes we just have to accept that some proofs are over our heads, and trust that if the Nobel laureates and acknowledged math wizards of the world say "it's so", then they're prolly right.

 

I find Turing's "halting problem" to be just barely within the boundary of my ability to understand.

 

However, Goedel's "incompleteness theorem" is just a smidge outside the boundary. No matter how much I tackle it, and from what direction, there is a point where my brain just goes "ppffftftftphhhhht".

 

One of the reasons I switched from Physics to Computer Science in graduate school was that I could not understand the derivation (or the proper use) of the Green's Function.

 

Many are called. Few are chosen. :confused:

[phillip1882]

"phillip,

you know, sometimes we just have to accept that some proofs are over our heads, and trust that if the Nobel laureates and acknowledged math wizards of the world say "it's so", then they're prolly right."

 

awwww, but its so much fun questioning authority.

admittedly my interpretation could be wrong. for example what turing might really be saying is that H and H' keep calling eachother back and forward. then i can see how a contradiction would arise. that is though the universal halting problem could recognise any infinite loop, it couldn't recognise that it itself was in an infinite loop, and you would need a new universal halt for this problem.