# Turing machine halting problem

• So the halting problem is definitely unsolvable on turing machines. But then, dereferencing a pointer on a turing machine takes more states than there are possible values for the pointer, and it gets even worse when you have to dereference another pointer before you can discard the first memory location.

And that's not even considering that nobody has successfully built a machine with infinity bits of memory yet, so whether a program runs on a turing machine isn't the same as whether a program can be run by real people in real life.

So how about we solve the halting problem for a machine with a total of N bits of memory, okay? I'm including CPU registers in there, and also cache and various other hardware states if they apply to the program. Also, you can write to disk, but then you'll have to include the entire disk in the number of bits, and if you access the internet, you'll have to total the number of bits for all machines currently attached to the internet.

Anyway, here's the algorithm:

1. Allocate 2N bits of memory.
2. Run the next instruction in the program.
3. Convert the machine's state into an integer x.
4. If the x'th bit of memory is set, the program does not halt.
5. Otherwise, set the x'th bit of memory and start again from step 2.

Now, if your computer has 1 byte of state, you'll need 32 bytes of memory to solve the halting problem. For 32 bytes of state, you'll need 14474011154664524427946373126085988481658748083205070504932198000989141204992 bytes of memory, and so on.

• Broken tooltip on Firefox 40, Win8.1 ...

• No repro on Chrome.

Also, solving the halting problem recursively 3 times requires a 34856892121032617929865715700930417996503484368953595585544346596340580889062 decimal digit number of bits for N.

To put that another way, you'd need 0.035% of the number of atoms in the observable universe to represent the number of bits of memory you'd need, assuming you can make something that stores a decimal digit in the average volume of an atom.

• The halting problem is solvable if you add a third output of "cheating" if the input program tries to use the value of whether or not it itself halts.

• or you could just install windows on it, that way you know for sure it's gonna halt sooner or later.

• How do you decide whether an input program solves the halting problem in your halting problem solver?

For my algorithm, which I am going to call Lubar's Algorithm because nobody could have possibly come up with this before, the paradox is avoided by making it impossible to run the halting problem solver on the machine it's simulating.

• So how about we solve the halting problem for a machine with a total of N bits of memory, okay?

Unless I misunderstand you, that is called a linear bounded automaton, and its language is decidable.

• You could probably get by with a history of memory diffs after each instruction - to check if there's loops, you'd run through the entire history once, and then again for every step inside that run seeing if memory ever matched with itself.

This of course assumes there is no external input, such as a filesystem (unless the entire filesystem is cached in RAM) or keyboard input or sound input or network cards.

• Which is larger: a list of up to 2N items that are each a pointer, or a 2N-bit integer?

• Ah right I get you. I misread it and thought you were storing an entire RAM image after every instruction, because I'm an idiot. Still, if the program had a lot of static data (and this wasn't recorded as differences) and a relatively short runtime before halt or loop you'd probably come out on top recording differences.

• How do you decide whether an input program solves the halting problem in your halting problem solver?

You just check if the program calls your solver program to get the output? You're not actually running the program, so...

• In response to this, I refer you to the work of one Kurt Gödel. The key implication of the incompleteness theorems taken as a whole is that any mathematical system formulated to prevent paradoxes is incapable of deciding at least one class of mathematical proofs. Since the whole point of the Universal Turing Machine is to provide a theoretical model of the limits of mechanizing mathematical logic, any system less complete than a UTM would not be able to prove a theorem that cannot be proven on a UTM.

While it is true that the Church-Turing Thesis (that all decidable theorems in any consistent formulation of mathematical logic can be decided by a UTM, or by a Turing-equivalent formalism such as a register machine - which is basically a super-set of what you're proposing - the lambda calculus, combinatory logic, or general recursive functions) is not proven and probably not provable, the provability of that particular assertion isn't at stake; what is at stake is the theoretical computability of the Halting Problem, and the first thing Turing did was prove that no machine less powerful than a UTM could decide it.

• No, I proved that you can solve the halting problem for a machine less powerful than a UTM, not on a machine less powerful.

Because computers have finite memory, so all you'd have to do is run the program on a machine with sufficient memory to keep track of which memory states the program has reached.

• For my algorithm, which I am going to call Lubar's Algorithm because nobody could have possibly come up with this before, the paradox is avoided by making it impossible to run the halting problem solver on the machine it's simulating.

There are type theories that try to do that sort of very specific exclusion. It's way too late for me to remember what they're called, but that's very much not a new idea. (I think they also go for an infinite hierarchy so that theory Tn can talk about theory Tn-1 without trouble, with T0 being the highly excluded version you're talking about and T being the standard UTM theory.)

The real problem is that it doesn't take much space at all to create a completely undecidable program (excluding the actual decision procedure itself) where it terminates exactly when it doesn't terminate and vice versa. All the stuff except the decision procedure is really very simple indeed. The only correct conclusion is that this is a clear non-existence proof of the decision procedure; anything else gives you complete nonsense. (Other presentations of decision procedure are tractable, and trivially easy to write. For example, allowing an extra “I don't know” response makes it into code that you can write in an afternoon for at least a reasonable set of simple cases.)

Of course, the right conclusion from the works of Gödel is that there isn't a finite set of axioms from which all of mathematics can be derived. There's always another statement which can be accepted or denied to introduce another axiom that couldn't be otherwise deduced. I've no idea what this means when converted into a UTM. It's way too late at night for such reasoning. But I do remember that a full classic decision procedure (of the kind we know is impossible) would also work as an oracle for mathematical proofs; proofs are isomorphic to terminating programs, after all.

they are marked as being published on the same day.

your link does not actually publish the time of publication, just the date.

@ben_lubar posted the OP at 02:45 (which i assume is local time, so that would be 06:45 UTC)

given the day is 24 hours long i conclude that statistically it is probable that @ben_lubar posted first and your link is a scummy content scraper.

perusing the content in the Humor category i think that for some rasin that site is scraping TDWTF for content....

http://lifeskillslist.com/■■■■■■■-does-not-exist/

• http://imgs.xkcd.com/comics/halting_problem.png

ah yes....

the answer to the halting problem: "Yes, your calculation automaton will eventually halt. .... oh, you wanted to know if it would halt because it completed its task rather than because it broke? Well you should have asked for that first! I'm sorry but I've already given you your allotted answers for this life. Please try again next life."

• perusing the content in the Humor category i think that for some rasin that site is scraping TDWTF for content....

Hmm...

Dear Sashi Kanojo,

You appear to be scraping content from what.thedailywtf.com without attribution.

A small selection of examples:

The `(original)` bits were links to the original posts.

• Can we XSS these guys?