Halting Undecidability proof faulty?

[Kriminal99]

Moderation note: This post was used to start a new thread discussing the same subject as this existing thread, so it and responses to it were merged with the old thread.

 

The proof is easily defeated by pointing out that we are assuming that a halting function couldn't just piecewise assign "halts" to itself instead of actually running on itself, which would prevent the existence off any partial function which would attempt to have the halting algorithm run on it's own encoding

 

 

Also, Consider the following proof.

 

Consider a set of Universal Turing Machines that at some point simulate their input machine. Call the set S.

 

Now we construct another set of machines "G" that takes the encoding of an element of S and copies it, then simulates S on it's self.

 

G is a subset of S. Therefore G can run on itself. G(G) infinitely loops as defined because it copies it's own input and simulates, then the simulation copies, then simulates, and that simulation copies then simulates etc. forever.

 

Thus any function G of this sort can not be claimed to be able to do anything BUT loop when run on itself. Thus any proof which depends on the creation and running of such a function on itself and claims that the function retains some ability other than looping is assuming a falsehood. All Halting proofs assume this falsehood, which is the source of the derived contradiction.

[alexander]

this is like a 1/4 of an idea... can you please expand on your first post with the following:

 

firstly, provide the basis of what lead you to look at this, otherwise why would it interest us? and posts that dont interest don't get replies you are perhaps looking to get.

 

secondly, explain halting to people who may not know what it is, this is, after all, a public forum where people come to learn and participate and get ideas or answers...

 

lastly, you say "source of derived contradiction"... what contradiction? this is something that should probably be covered in the pre/intro, but still, consider structuring your post closer to an essay (intro paragraph, or sentence or something, some words describing your problem/delema, introduce the concept, ask questions, post oppinion, close out with some thoughts or more questions), it makes for an easier read, better interest into researching the matter and all around a better discussion.

 

P.S. don't take me as a prick, and i do what you did in your post all the time, problem is, over time i have developed an understanding of better or worse ways of asking/discussing and creating posts that draw people into conversation, rather then confuse the living hell out of them and make them simply not care, which, as you may imagine, translates into no replies and your frustration with the user base for not helping you get a fresh view point, or bring to your eyes some evidence that you did not consider before.

[phillip1882]

the halting problem is not saying you can't determine whether a particular program will halt.

its saying there's no universal program to determine whether any program will halt.

let me show you what i mean.

 

let's say we have the program

x =0
while x <10:
  x = x+1
  x = x-1

and want an algorithm to determine whether or not this program will halt. we note that x goes back and forth between two numbers 0, and 1. so one possible algorithm would be

if x value resets, the program will never halt.

now however consider

y = 0
while x <10:
  y=y+1
  x = 0
  x = y

the x value resets every iteration, but then quickly goes to the value y. so we need a new algorithm. one possible algorithm would be, if x repeats its pattern, the program will never halt.

now consider

y = 0
while x <10:
   y = y+1
   x = 0
   x = 1
   if y = 10:
      x = 11

x repeats its pattern 10 times, yet the program still halts.

in short there is no algorithm that will guarantee an accurate halt detection.

[alexander]

I understand what halting is, i am just saying that a clarification, like the above, would make other people more prone to participate in the discussion.

 

 

how about an algorithm that first takes note of the condition under which a particular event is supposed to halt.

 

notes the conditions under which any explicit brakes in the particular process will occur, and what variables will effect those conditions.

 

steps through the decision process a couple of times, to see how the variables that effect the exit conditions are changed.

 

finally determines if any of the conditions that cause the algorithm to exit will ever exist.

 

sounds like some self-modifying code actually to be smart enough to create a child that will monitor the explicit loop conditions...

[phillip1882]

well consider the following code

while z <100:
  y = random.randint(0,100)
  x = random.randint(0,y)
  z = random.randint(0,x)

this should halt, but it could take hours, and there wouldn't be much of a determinable pattern.

[alexander]

Actually that code will never halt, because while you may have a random number equal to 100, your algo will never return z that is larger then 100.

 

and yes, looking at exit conditions and variable manipulation limits, my algorithm, if implemented properly, will still be able to detect a non ever-ending loop...

[CraigD]

well consider the following code

while z <100:
  y = random.randint(0,100)
  x = random.randint(0,y)
  z = random.randint(0,x)

this should halt, but it could take hours, and there wouldn't be much of a determinable pattern.

Though a bit off the topic of the halting problem, the questions raised by Phillip's example of a program that uses a random number function can shed light on some important characteristics of Turing machines.

 

Although a real computer can have a “true” random number function via special hardware or clever use of ordinary hardware (see the wikipedia article section ”Generating random numbers from physical processes”), none of this hardware is available to a Turing machine, which is completely deterministic. While you could write a Turing machine that generates pseudorandom numbers, or even an implementation of a python interpreter that could run the code above, given the machine and its initial tape (which would contain symbols corresponding to a specified python random.seed(x) value), it would be possible to determine the exact value of z at any point in the program’s execution, which would coincidentally also determine exactly when it would halt.

 

The key point I’m trying to make is that, although they can be similar enough for practically any purpose, the pseudorandom numbers that can be generated with a Turing machine are not truly random, or in principle any less deterministic than the values in the examples in Phillip’s previous post.

 

Assuming that true randomness exists (an uncertain philosophical and physical assumption), if the quoted program were run with the random module configured to use a true random number generator (eg: a chip that detected decay events of a radioisotope sample, not just at seed time, but continuously), when, or even whether, the program would halt would be truly impossible to determine, as a small but non-zero probability of it running for an arbitrarily long time would exist.

[CraigD]

while z <100:
  y = random.randint(0,100)
  x = random.randint(0,y)
  z = random.randint(0,x)

Actually that code will never halt, because while you may have a random number equal to 100, your algo will never return z that is larger then 100.

This code will finish on average after [math]101^3 = 1030301[/MATH] iterations of the loop, because random.randint(0,100) can return integers including 0 and 100, and “100 < 100” evaluates to false.

 

Alexander, perhaps you’re confusing python’s random.randint with the random function of other languages, where RANDOM(100) typically returns no integer greater than 99? Or confused “<” for “<=”?

[alexander]

no its all in confusing the signs, and i nearly always have to look them up, i miss read that as z>100, that's all....

 

and my algorithm will still hold true, seeing that the set of values that z can be will be [math]z \in 0 \le z \le 100[/math] which with a condition of z<100 will evaluate to true for a loop exit.

[Kriminal99]

this is like a 1/4 of an idea... can you please expand on your first post with the following:

 

firstly, provide the basis of what lead you to look at this, otherwise why would it interest us? and posts that dont interest don't get replies you are perhaps looking to get.

 

secondly, explain halting to people who may not know what it is, this is, after all, a public forum where people come to learn and participate and get ideas or answers...

 

lastly, you say "source of derived contradiction"... what contradiction? this is something that should probably be covered in the pre/intro, but still, consider structuring your post closer to an essay (intro paragraph, or sentence or something, some words describing your problem/delema, introduce the concept, ask questions, post oppinion, close out with some thoughts or more questions), it makes for an easier read, better interest into researching the matter and all around a better discussion.

 

P.S. don't take me as a prick, and i do what you did in your post all the time, problem is, over time i have developed an understanding of better or worse ways of asking/discussing and creating posts that draw people into conversation, rather then confuse the living hell out of them and make them simply not care, which, as you may imagine, translates into no replies and your frustration with the user base for not helping you get a fresh view point, or bring to your eyes some evidence that you did not consider before.

 

 

Hey thanks. I am not sure I agree that bringing up all the details you mentioned is completely necessary, but if you want me to sure why not.

 

I have learned material from many subjects in the past, and I have used all of this information to build a single network of information in which everything fits together. One of the subjects I have studied, and which I believe forms a large part of the root of this network, is epistemology. In this subject and other philisophical subjects I have found a large number of very useful concepts many of which were discovered in ancient times. Most of these ideas are very general in nature and apply to almost every other discipline in more specific forms (hence them forming the root).

 

As I look into more specialized subjects, I notice something that disturbs me somewhat. Many of these general concepts which I have learned are not understood by specialists despite the fact that such concepts still govern the specialty and are important to understand.

 

Some of these ideas have been championed by other disciplines (such as formal logic) and others have simply been forgotten by mainstream academia.

 

In any case I see these fundamental truths and others violated hundreds of times a day by people with different levels of understanding. More relevant to this discussion I sometimes see fundamental principles of human knowledge violated by mathematicians.

 

For example, the word proof is tossed around callously when in fact there is no such thing as proof of anything. There is no form of proof that gaurantees that at some point in the future the claim will not be debunked, since one of the premises can be debunked and close study of the limits of induction will show you exactly what kinds of cases it is more likely to occur in.

 

The halting undecidability proof is exactly one such "shady proof". It has a large number of unrecognized assumptions, or at least more than a person can easily recognize.

[Kriminal99]

the halting problem is not saying you can't determine whether a particular program will halt.

its saying there's no universal program to determine whether any program will halt.

let me show you what i mean.

 

let's say we have the program

x =0
while x <10:
  x = x+1
  x = x-1

and want an algorithm to determine whether or not this program will halt. we note that x goes back and forth between two numbers 0, and 1. so one possible algorithm would be

if x value resets, the program will never halt.

now however consider

y = 0
while x <10:
  y=y+1
  x = 0
  x = y

the x value resets every iteration, but then quickly goes to the value y. so we need a new algorithm. one possible algorithm would be, if x repeats its pattern, the program will never halt.

now consider

y = 0
while x <10:
   y = y+1
   x = 0
   x = 1
   if y = 10:
      x = 11

x repeats its pattern 10 times, yet the program still halts.

in short there is no algorithm that will guarantee an accurate halt detection.

 

Hey. There is a common thread in each of the programs that loop forever that is not in the program that does halt. Namely, there is a complete state or configuration that repeats. At one point, the program is at the same point with the same value for the variables. This is clear evidence of an infinite loop.

 

In the final code, this is not the case because y has a different value in each iteration.

 

There is another kind of infinite loop where values change, but they never go in a direction that will allow the program to halt. This is also easily detectable.

 

I suppose the most difficult question is to ask how does one know that a program that takes N steps toward a ending value (x - n; if (x < 10) {quit;} else {x + n + m;}) then M steps back halts or not in general.

[alexander]

Kriminal, thank you, that makes for a much more engaging conversation... really does, seeing where you are coming from, helps build replies that cater to what it is that you seek.

 

The thing with math, as well as any science is the fact that the facts claimed are facts that are proven to any arbitrary case we can come up with at the current time. Not to be confused with theories, but you were not implying those anyways. These facts are to our understanding facts, axioms, something so fundemental to math that many later concepts are built on them. But like any science, and math is a science of numbers, in many things it is not certain, thus is prone to, and accepts change. Proofs are proofs, they prove the concept to some degree, some prove it to n'th degree, where for any value you can give it, the concept remains true, others are proven, sort of, beyond current reasonable doubt, though if your reasoning changes, the proof may fly out of the window. I think it takes an understanding of what science is to understand this difference between "facts" and "things we know"...

[phillip1882]

alexander, i have no doubt that you could write an algorithm that determines whether a particular program will halt, and may even work for 10,000 algorithms. but there will always be a 10,001 algorithm that it doesn't work for.

 

for example so far i've posted code that the human brain could easily determine would halt or not, but i could just as easily post code that even i couldn't read and determine whether or not it halts, even after running through the loop a few times.

[alexander]

well, lets write an algorithm that will determine all that.... lets start a new thread, select a language to use because the algorithm will be extremely language specific, and go at it with pseudo code, can't be all that hard....

[Kriminal99]

Kriminal, thank you, that makes for a much more engaging conversation... really does, seeing where you are coming from, helps build replies that cater to what it is that you seek.

 

The thing with math, as well as any science is the fact that the facts claimed are facts that are proven to any arbitrary case we can come up with at the current time. Not to be confused with theories, but you were not implying those anyways. These facts are to our understanding facts, axioms, something so fundemental to math that many later concepts are built on them. But like any science, and math is a science of numbers, in many things it is not certain, thus is prone to, and accepts change. Proofs are proofs, they prove the concept to some degree, some prove it to n'th degree, where for any value you can give it, the concept remains true, others are proven, sort of, beyond current reasonable doubt, though if your reasoning changes, the proof may fly out of the window. I think it takes an understanding of what science is to understand this difference between "facts" and "things we know"...

 

This discussion is a bit abstract for me. It's not really clear what you are saying exactly. Give an example perhaps?

 

Or maybe I can. I can prove that 1 + 1 = 2 just by putting two apples together and seeing that there are two of them. One can still doubt, but to do so in this case is to doubt everything that a person sees and if you are going to do that then you have nothing to go on at all.

 

Other than these trivial cases, it seems a "proof"'s effectiveness has a lot to do with how much the audience knows - meaning you can "prove" things that are wrong to people who do not know much, and to prove something that is right you have to start with what the audience knows and go from there.

 

The best understanding I can make of "proof" in academia is that there is some "body of knowledge" that it is assumed everyone is up to date on up to a certain point, and it is from there the "proof" starts. If you aren't up to date, you are supposed to look back and find a sequence of proofs that gets you there.

 

The problem with this is that epistemology isn't fully included in this body of knowledge. Usually proofs stay pretty formal, but sometimes they slip into this sort of "storytelling mode" where the person stops manipulating symbols for a moment and starts talking about what they can and can't do and why. In this situation, it seems there is a strong danger of there being unrecognized assumptions and I find myself at every step asking "OH REALLY? Can we REALLY do that?". In other words, at this point it is just an argument and no longer a proof.

 

The thing that makes me different in this regard is my advanced skepticism, which does seem to be a trait necessary to do proofs at all and yet there does still yet seem to be a stage of it that is never reached by most in the field. I am guessing that stage is the one where you are skeptical of something even though the majority of people around you agree with it.

[alexander]

I can certainly provide an example.

 

Euclid's Parallel postulate states, well rather Playfair's rendition of that postulate states that at most one line can be drawn through any point not on a given line parallel to the given line in a plane. It is and remains an axiom, however the further mathematicians looked at space, and the fact that it is not always, or nearly ever is it flat, that concept had to be changed later, when looking at non-flat spaces, and planes that bend and curve, the geometry that made many current physics theories possible that axiom had to be changed to accommodate a new way at looking at things, where the Euclidean postulate still holds true for it's range, a postulate stating that more than one line that can be extended through any given point parallel to another line of which that point is not part, is one of the fundamental postulates in non-euclidean geometry (i.e. elliptic curve and hyperbolic geometries).

 

This is an example of how something once thought to be true, while still being true, had to be changed to suit a different theory of looking at things.

 

By the way, both postulates hold true, it just depends on which perspective you look from...

[Pyrotex]

The only part of that the proof does not explicitly state is the part about tracing the computations. So we are left to wonder how on earth the Halting Machine would operate without tracing the input machine.

But that is irrelevant....

No. It is ENTIRELY relevant.

 

It demonstrates that YOU do not understand how a Halting Algorithm would operate.

 

Say, Krim? Don't they make medications now for Compulsive Defiance Syndrome? :hyper: