Wikipedia:Reference desk/Archives/Computing/2015 August 14

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 14

What is the shortest program that's an example of the halting problem?

What is the shortest concrete program, if possible in ruby, is undecided when we want to know whether it will halt? I am pretty sure

> puts 'Hello, world!'

halts. --Denidi (talk) 00:44, 14 August 2015 (UTC)

Not familiar with Ruby, but couldn't you set a variable equal to something random-ish and then loop infinitely if it's below a certain value? (The halting problem proof itself isn't much more sophisticated than that, is it?) Wnt (talk) 00:57, 14 August 2015 (UTC)

That doesn't work. Computers can't generate truly random numbers (well "Turing machines" can't - and that's what we're talking about here) - pseudo-random numbers aren't random, so a hypothetical "DoesItHalt" function could simply examine how the random number generator had been implemented, how it was initialized and decide the answer from that. SteveBaker (talk) 14:25, 15 August 2015 (UTC)

I don't understand it, but I am trying. I was under the impression that we can not tell even whether a well-written program will terminate, provided this program reaches a certain complexity. It's kind of easy to find examples of infinite loops if you expect to act on a condition that never happens.--Denidi (talk) 02:16, 14 August 2015 (UTC)

The proof of the formal undecidability of the halting problem really is complicated. It is the proof of Godel's incompleteness theorems put into Turing machine form, and the proof of Godel's theorem involves what is essentially a self-referential trick. I remember once reading, in the 1980's, that someone was selling a program known as the Basic Infinite Loop Finder (BILF), which was designed to determine whether a BASIC program contained infinite loops. It was itself a BASIC program, and the input to it was another BASIC program. The author tried to explain to the vendor that what he was selling couldn't be done, because finding infinite loops is the halting problem. The author then paid the vendor $20 for the program. The program ended with either of two double statements: PRINT "THIS PROGRAM DOES NOT CONTAIN INFINITE LOOPS."; STOP, or PRINT "THIS PROGRAM CONTAINS AN INFINITE LOOP."; STOP. (Note: I've used the semicolons, not part of BASIC, for readability.) The author then deviously switched the two double statements at the end of the source program when making it into the object program. He then started it running on a Friday. On Monday, it was still running. The determination of whether the program would halt didn't halt. However, my point is that the proof of the halting problem, like Godel's theorem, of which the halting problem is the first practical example, involves a self-referential trick and is not simple. Robert McClenon (talk) 02:29, 14 August 2015 (UTC)

(Edit conflict) The halting problem consists of devising an algorithm which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input. Wnt's example is just a variation of "if input equals 1, halt. If input equals 0, loop forever" with a random number generator picking the 1 or 0, and thus fails the requirement that the decision procedure must work for all programs and all inputs.

More generally, if a program makes use of a true random number generator (something based on the time it takes for atomic decay, for example), the output of the RNG is an input to the algorithm, not a part of the algorithm itself. If a programming language uses a pseudo-random number generator without a random seed, the RNG is deterministic and gives the same answer every time you run the program. If it does have a random seed, the seed is an input, not part of the algorithm.

Getting back to the Ruby program, the halting problem is theoretically decidable for deterministic computers with finite memory. Such a computer has a finite number of possible states, and thus any deterministic program running on such a computer must eventually halt or repeat a previous state and loop forever. I can write a program that runs on a microcontroller with 256 nybbles of RAM that will take far, far longer than the age of the universe to repeat states, and Ruby has access to far more memory than that (though still a finite amount) so the halting problem is theoretically decidable for any Ruby program, but practically undecidable.

Here are some examples of problems that no algorithm can solve, and programs that are solvable but not in a reasonable amount of time. [ http://www.cs.bris.ac.uk/history/teaching/algorithms/chapter5.html ]. ...and, of course, there is this... --Guy Macon (talk) 10:17, 14 August 2015 (UTC)

A program that computes the Collatz conjecture would be pretty short. Programs that compute other unsolved problems may be relevant. 91.155.193.199 (talk) 11:37, 14 August 2015 (UTC)

I agree that computing Collatz is easy - in C++, it's one line of code:

void collatz ( int n ) { while(n!=1)n=(n&1)?(3*n+1):(n/2); }

So if you call that function with a large random number then if the collatz conjecture is true, it'll always halt. But if the conjecture is false, then for some input, it will loop forever. We don't know whether it'll halt or not because we mere humans have yet to either prove or disprove the collatz conjecture.

There are two problems with this with regard to the halting problem:

1. On a real computer, with only 2³² possible values of 'n', we'll undoubtedly halt every single time because the conjecture has already been tested up to that value - we'd need more precision (which is do-able with variable precision integers) - and possibly an infinite amount of memory to hold that number if the collatz conjecture is false. So a practical implementation on an actual, for real, computer will always halt regardless of whether collatz is true or not. It's possible to find programs that have undecidable halting state on an infinite computer - but we're talking about one with finite resources.
2. The problem with collatz is that it's only a conjecture. It could easily be that the conjecture is true and that collatz(n) alway halts for all possible values on 'n' - so this program may very well halt for absolutely all finite integers.

There is no evidence that collatz is false - or that the question of whether it's true or false is undecideable. We simply haven't proved or disproved that conjecture yet. All we can say is that until collatz is either proved or disproved, we mere humans can't tell whether this program always halts or not.

But that doesn't necessarily mean that some hypothetical halting-program decision maker would be unable to tell. Suppose I were to write a successful halting test - then I could run it on my collatz program and either prove or disprove the conjecture. If we had a halting test, we'd solve an enormous number of mathematical problems using it. However, we do know that we can never produce such a test.

Here is an informal proof that nearly everyone can understand:

1. Suppose the halting problem could be solved...that we could write some C++ function: bool DoesItHalt(char *program) - which when fed with the source code of a C++ program would look at it carefully and return 'true' if the program will halt and 'false' if it won't.
2. Now, I can write a new program: while ( DoesItHalt ( program ) ) /* Loop */ ; - this program will halt if the program it's fed DOESN'T halt - and run forever if the program it's fed DOES halt.
3. Finally, pass that program it's own source code. If the program halts then it won't halt and if it doesn't halt, it will halt. Clearly this is a paradox - and therefore it is impossible to write the DoesItHalt function...and that means that the halting problem is impossible to solve.

What we need to write a program that we can never know whether it halts or not is to find some mathematical conjecture which has been proven to be unprovable. Something from List of undecidable problems perhaps.

The "The mortal matrix problem" for two 15x15 matrices seems plausible here. SteveBaker (talk) 16:54, 14 August 2015 (UTC)

@SteveBaker: The problem with using "some mathematical conjecture which has been proven to be unprovable" — is that there aren't any. This is a common confusion between two senses of the word "undecidable".

The halting problem is undecidable absolutely. You don't have to consider it relative to any deductive system or other epistemological framework, and it has bupkes to do with our state of knowledge about any question about whether a particular program halts on a particular input, if you're allowing inputs.

There's a very different notion of a proposition being undecidable relative to a formal theory. That's the one you seem to be talking about. But that can only ever be relative, never absolute. Every proposition is decided by some formal theory.

Now, what I'm writing is at the most basic, cut-and-dried, mathematical level. If you want to go more philosophical, there are thinkers who have proposed that there could be such a thing as an absolutely undecidable proposition in terms of not being decidable by any justifiable formal system (as opposed to any formal system at all). Peter Koellner has a really superb paper on this, here. But that's way outside the scope of this discussion, because no one has managed to "prove" that any particular proposition is in this category. --Trovatore (talk) 02:08, 15 August 2015 (UTC)

@Trovatore: Thanks. I'm not sure I understand the two different meanings of "undecidable" in this context. (In the context of the halting problem, we're discussing a turing machine - so "inputs" are a part of the program itself...they have to be written onto the 'tape' before the machine is started up.) But isn't it the case that, because we're talking about computer programs, our discussion is constrained to Turing machines, and that is the "formal theory" in which our propositions are framed? So we don't need a program that some hypothetical system could determine as halting or not - we only need one that another computer program would be unable to so determine. So my gut feeling is that such a program could exist. Albeit only for a machine with infinite memory (Turing machines are assumed to have infinite memory - so that's perfectly OK).

Either way - the article List of undecidable problems should probably be extended to explain the distinction you make between those two meanings. SteveBaker (talk) 14:15, 15 August 2015 (UTC)

The example I use is the function: IsThisNumberInPi(number). It returns true if the number provided is a substring of all the digits of pi. It returns false otherwise. Since it is unknown if Pi ever ends and it is unknown if EVERY possible sequence of numbers is in Pi, it is not possible to tell if this function will ever halt. This does not prove that the halting problem is unsolvable. It is merely an example of a program with an unknown status of "will it halt". 209.149.114.32 (talk) 19:09, 14 August 2015 (UTC)

Actually, it IS known that pi never ends. There are any number of proofs that it's an irrational number. If it ended then you could express it precisely as the ratio of two numbers. Every test that's been done on the digits of pi show them to be statistically random - which would mean that eventually your program would halt - but we have no absolute proof of that. The fact that we mere human beings don't know whether pi has every combination of digits in it doesn't mean that a hypothetical program couldn't figure that out in the course of testing IsThisNumberInPi. We don't know that this is an unknowable thing. SteveBaker (talk) 14:15, 15 August 2015 (UTC)

OK, someone may have covered this above; I haven't read all the many contributions. I just want to sum up the important takeaway in a short response.
The answer is that there is no individual program such that it's "undecidable whether it halts". Or at least, the undecidabilty of the halting problem does not say there is.
What the undecidability of the halting problem says is that there is no general algorithm that decides correctly, for every program, whether that program halts. It doesn't mean there's any individual program whose halting is "undecidable". --Trovatore (talk) 19:37, 14 August 2015 (UTC)
To be clear, I'm talking about programs without inputs. Programs with inputs are a different question — then the question is not "does program P halt" but rather "does program P halt when given input I". Nothing changes in what I wrote above, except that you always have to talk about program–input pairs rather than programs, so it's longer-winded. --Trovatore (talk) 01:51, 15 August 2015 (UTC)

@Trovatore: Yes, in the context of the halting problem, "input", "data" and "program" are synonymous - they are all stored on the tape of the Turing machine. If a program requires an input (like my collatz function) then that input is considered to be a part of the program. Also, you can't rely on "random numbers" because Turing machines (and therefore computers) are deterministic systems and can only generate pseudo-random numbers. SteveBaker (talk) 14:15, 15 August 2015 (UTC)

Aha! I have the answer to the OP's original question: No such program is possible on a computer with finite amounts of memory - such a program is possible for a computer with infinite memory. Here's why:

OK - so there are indeed two programs involved, the "DoesItHalt" testing program (call it "DIH"), and the program that's being tested: "UnknownWhetherIHalt" ("UWIH"). We know that DIH is impossible to write for arbitrary inputs...the proof of that is very simple (see above). We could of course imagine a DIH" program that would work some of the time (eg: It would search the source code for loops and recursion - and say, conclusively, that the UWIH will definitely halt if there are none of those things...and it could look for "while(1);" statements and say that a program that executes that statement will definitely never halt. But we know that some kinds of programs would fool it, no matter how clever it is. Some of the time it must either say "I don't know" - or itself fail to halt.

That says that there simply must be UWIH programs for which no test could be devised to determine whether they'll halt or not...and our OP would like us to provide a small example of such a thing...which sounds easy enough...but maybe isn't.

One concern that has been raised is whether it's possible to write UWIH for a machine with a finite amount of memory. The concern is that a finite machine can only have 2^{number-of-bits-in-memory} possible states - and that means that the machine must return to a previous state after at most 2^{number-of-bits-in-memory} cycles and therefore can never halt. This means that any program running in a machine with finite memory will either halt or return to a previous state within 2^{number-of-bits-in-memory} cycles. So the DIH program could simply execute UWIH one instruction at a time for that number of cycles and note whether it ever repeats a previous state (or halts) in the process of doing that.

That algorithm will work for any program that can only consume finite amounts of memory. DIH only fails when the UWIH program can consume infinite amounts of memory and thereby never return to a previous state, no matter how long it runs.

So, the answer to our OP's question is that we could probably write such a program, but it would have to be run on a machine with infinite memory.

If there is infinite memory, (or if we're talking about a program that we just want to think about, and not run 'for real') - then I think we need a undecidable mathematical proposition...not an "undecided" proposition like collatz...a proposition that we can conclusively prove cannot be proven. Godel's Theorem guarantees that such things exist - and I believe that there are a few like that which we know about. The "mortal matrix problem" for two 15x15 matrices seems to be one of them. So if we wrote a program that multiplied any number of copies of two 15x15 matrices together in every possible order - testing to see whether a zero matrix resulted - then we know (for sure) that we can never know whether that process will ever find a zero matrix. So a simple program that does that is a great example of UWIH - except that the numbers in those matrixes will have to be stored at infinite precision.

So that's likely to be a fairly small program, under 50 lines of code, maybe - that we know would fool DIH - but only in the theoretical case where the numbers in the matrix are stored at infinite precision.

SteveBaker (talk) 02:04, 15 August 2015 (UTC

No, no, no, Steve! Goedel's theorem does not guarantee that such a thing exists! That's what I was explaining up above.

What Goedel's theorem guarantees is that, for any particular formal theory T satisfying certain conditions we don't need to go into here, there is some statement S such that T does not decide S.

It doesn't mean there's an S that can't be decided at all! You just might need more than T to do it. --Trovatore (talk) 03:10, 15 August 2015 (UTC)

@Trovatore: But here we're talking about a real computer program - so we've constrained everything to the domain of a Turing Machine...so (if I'm understanding the math correctly...and I very well may not be!) T is the description of a Turing Machine with a 'HALT' instruction. Doesn't Godel guarantee that there is an S that is undecidable by a such a machine? We're not saying that there can't be some miracle machine that's somehow different...better than a Turing Engine...that could decide whether our program halts - only that there isn't another computer program that can do it. SteveBaker (talk) 14:15, 15 August 2015 (UTC)

So there is a correspondence here. For a formal theory T and a statement S, there is a Turing machine M that searches for a proof of S in T, and halts if it finds it. Is that what you're getting at? I'm not quite sure.

Anyway, what the undecidability of the halting problem says is, suppose there's a "deciding" Turing machine M_D, that accepts as an input a different Turing machine M_C (C for "candidate"), written onto M_Ds initial tape if you like (but M_Cs initial tape is empty; no inputs). Then M_D is supposed to decide whether M_C halts. The undecidability result says that, for any such attempt to construct M_D, it must fail on some M_C. When given that M_C as input, either M_D halts and gives the incorrect answer, or else it never halts at all and therefore gives no answer.

But you can't reverse the quantifiers. The result does not say that there's some M_C such that no M_D decides it correctly.

In fact, that's easily seen to be false. Because M_C either halts or it doesn't (law of the excluded middle). So construct M_D1 to accept M_C as input and immediately assert that M_C halts, and M_D2 to do the same thing except it immediately asserts that M_C doesn't halt.

Then either M_D1 or M_D2 is correct (albeit we may not be able to determine which). Therefore the idea of being able to reverse the quantifiers and come up with a Turing machine that no Turing machine can decide whether it halts, is impossible. --Trovatore (talk) 17:53, 15 August 2015 (UTC)

The pi suggestion can run forever or it may halt. It doesn't require infinite memory to run forever. It only needs to maintain the last x digits of pi where x is the length of the input.

That's not true. There is an equation to find the N'th digit of pi - but it uses N as an input. A computer with finite memory will eventually run out of memory to store N. So, no...you can't do that. SteveBaker (talk) 04:40, 15 August 2015 (UTC)

---

As Trovatore said above, for every particular program, there is an algorithm that correctly determines whether it halts or not. For example, either return "halts" or return "doesn't halt" will return the correct answer. For the purpose of solving the halting problem, you only have to return the correct answer, not prove it correct. So there is no "example of the halting problem"; each candidate algorithm gives wrong answers for different programs.

A different question, which is not really related to the halting problem but may be what you intended to ask, is "what is the smallest program that we humans haven't managed to prove the halting status of?" This thread asks the same question. In the comments on the question there is a good candidate answer: "According to Wikipedia article on Busy Beaver there is 2-symbol 5-[state] [Turing] machine that is not known whether it halts or not [starting with a blank tape]."

Lychrel numbers give another short answer. According to the article, it is not known whether 196 is a base-10 Lychrel number. That means that no one knows whether this Python program halts (when run on an abstract machine with unbounded RAM):

    n = 196
    while n != int(str(n)[::-1]):
        n += int(str(n)[::-1])

The already-mentioned Collatz conjecture might also work, except that it has been verified up to very high numbers, and the highest number that has been tested is determined (as far as I know) only by when the latest tester got bored. There is no single starting number that has long resisted attempts to prove its fate, as there is with Lychrel numbers. You could test all natural numbers and halt when you find a loop that isn't 4,2,1, but that would require a longer program. -- BenRG (talk) 03:22, 16 August 2015 (UTC)

Editing Wikipedia over a VPN

I'm going to be going to traveling to China soon, and will be using a VPN (connected to my current IP address) to get around the Great Firewall. Aside from the issues of speed, will this have any effect on my ability to edit Wikipedia? I know that open and anonymous proxies are blocked, but this VPN (if Dad and I ever get it set up) should be secure and not anonymous. In effect, I should just be editing from my usual IP address like I am right now, but from China.

Just want to be absolutely certain that there's no way that could cause any problems. Ian.thomson (talk) 18:28, 14 August 2015 (UTC)

There will be no problems on the side of Wikipedia, but there may be some problems with the Great Firewall as it may block your VPN if it detects suspicious behavior. Ruslik_Zero 19:48, 14 August 2015 (UTC)

Expanding on what Ruslik said, Wikipedia just checks the IP address so it's fine, but China now blocks VPN traffic by deep packet inspection, so even a private VPN may not work. This page has seemingly up-to-date information about which protocols are blocked, but the situation could change at any time. -- BenRG (talk) 04:30, 16 August 2015 (UTC)

Ha, thanks for that. My family did our own setup, but one of the protocols most recommended in that article (and that site) was the only one we could get to go through our home security. Will probably skip over the stuff to avoid any advanced deep packet inspections specifically targeting me (should they choose to do so), since I have no intention of raising their suspicions just to watch cat videos.

"Sir, I think we've found a spy!" "What's his activity?" "He's... watching a ten hour loop of some cartoon muscle man singing falsetto. Sorry sir, nevermind." Ian.thomson (talk) 20:06, 17 August 2015 (UTC)