14 ms·
The halting problem is decidable on a set of asymptotic probability one (2006)
- dgacmu 3y agoIn case anyone wants a quick tl;dr: as the length of a program (expressed as the number of states in a Turing machine) grows, the relative fraction of undecidable programs decreases. In other words, "most" (approaching "nearly all" as they get longer) Turing machines, out of the set of all possible Turing machines of that same size, are actually decidable. (Though this doesn't tell us about whether most real programs are decidable, as the programs humans write also come from a small subset of the universe of Turing machines. But we know that in practice, this is also true). This relates nicely to the earlier discussion of SAT: while SAT is NP-complete, many instances can be solved in reasonable time. Similarly, we can verify that many actual programs will halt even if the problem is, in general, undecidable.
- bawolff 3y agoI think it would be pretty shocking if the opposite were true. I imagine most randomly generated turing machines are pretty trivial.
- mananaysiempre 3y agoDunno. The real numbers, for example, are in the “most things are eldritch abominations” camp[1]: the reals are uncountable, the computable reals are a(n everywhere dense) countable set[2] (that is therefore[3]) of measure zero. Not that there’s a reason to expect these cases to be similar, just that weird things do happen. [1] https://mathwithbaddrawings.com/2016/12/28/why-the-number-line-freaks-me-out/ https://mathwithbaddrawings.com/2016/12/28/why-the-number-li... [2] There’s a finite set of programs of a fixed length, thus (countable union of finite sets) a countable set of all programs, thus only at most a countable set of numbers they can compute. [3] Every countable set has Lebesgue measure zero: cover point #n by a blot of measure ε / 2^n (that could even intersect other blots) to prove all of them have measure at most ε > 0, take ε as small as desired.
- orlp 3y agoI've made the argument many times before that the reals are certainly an interesting set of objects, but a poor abstraction for the concept of a number. We should work towards replacing them with a more well-behaved set without eldritch monsters such as uncomputable 'numbers' that you can't add or multiply with. E.g. https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number.
- zeroonetwothree 3y agoComputable functions do also have some weird behavior. For example: a) all functions are continuous, b) equality is not computable (maybe not so weird for anyone used to floating point), c) differentiation is not computable unless you work over complex numbers (but integration is!)
- orlp 3y agoa) All functions from computable reals to computable reals are continuous. This makes sense, because an arbitrarily small input difference leading to an arbitrarily large output difference is not a good basis for computation. You can still have discontinuities for discrete computable maps. b) Neither is equality computable for the reals. Nothing is lost here. c) Differentiation is computable for the functions of computable reals if you have a computable rate of convergence.
- chromoblob 3y agoHow to do (c)? I tried to model the reals as lazily computed sequences of intervals with rational bounds where every next interval is subset of previous one, and couldn't write a higher-order differentiator function because on every step for a given input interval there is output interval with non-zero (in most cases) size and the differentiated function may contain quick enough oscillations that the derivative is unbounded, and thus the derivative will stay unbounded no matter what you do. What do you mean by rate of convergence?
- EscapeFromNY 3y agoMy intuition tells me the opposite. Suppose you have one undecidable statement, U, out of s possible statements. A random program of length n contains U at least once with probability 1-(1-1/s)^n. If the program is of infinite length, it contains U with probability 1. So I would have thought the chances of undecidability increase as the program gets longer. Clearly my intuition is wrong, per the paper, but I don't think the result is immediately obvious.
- zeroonetwothree 3y agoA statement in a program can’t really be undecidable on its own. It’s the program that has that property.
- chromoblob 3y agoA statement is just a subprogram. Whether it can be decidable depends on whether a single program can be undecidable (and I can't see how that could be possible, undecidability is property of the problem - decision procedure on set of programs)
- cyberax 3y agoThink about it like this, there are infinitely many Turing machine state classes that are easily decidable. For example, a simple infinite loop or its equivalent. Most of these classes are also very trivial to construct, and require only a few "instructions". So if you make a random TM, it's almost guaranteed that it'll get eventually "trapped" in one of these easily decidable infinite loops.
- EscapeFromNY 3y agoThanks, that's a perfect explanation
- bawolff 3y agoI think the chance of having an undecidable (group of) statements go up, but the chance of executing it does not. There isn't really a single undecidable statement, it would be a complex subroutine. My intuition would be its much more likely a halt or indef loop (both relatively simple) would appear before program control would transfer to the undecidable part, in most cases. I.e. if something undecidable requires 60 symbols in a row in correct order, but halting requires one, than probability of a halt at any given spot seems much higher on average.
- EGreg 3y agoAlso the same applies with the CAP theorem… it is mostly a theoretical result but in practice things go well the vast majority of the time! Also look up Buridan’s Principle by Leslie Lamport. I emailed him and “argued” with him for a while after reading his paper, but in a theoretical sense and some practical subsets it is correct!
- sebzim4500 3y agoInteresting paper. I agree that he is probably technically correct, but I think he downplays the fact that all over physics people say "never" when they mean "with probably less than 10^-1000. For example, in classical thermodynamics there is a nonzero probability that all the air molecules in a room will happen to travel to one side, violating many laws of fluid mechanics. In quantum mechanics the situation is even worse, where basically anything can happen with nonzero probability.
- galaxyLogic 3y ago> basically anything can happen with nonzero probability. It took me some time to realize that that's what "HitchHiker's Guide to Galaxy" was about.
- SilasX 3y agoI’m not sure the comparison to SAT is a good one because, in that case, we know of particular “phase transition” regions in which most problems aren’t clearly satisfiable or unsatisfiable. (Specifically, when the ratio of clauses to variables in 3SAT is about 4.2.)
- oldgradstudent 3y agoIt's an excellent comparison to SAT, because in both cases nobody cares about random instances at all. For non-random instances the ratio of clauses to variables in is utterly meaningless.
- zeroonetwothree 3y agoThe simplex algorithm is similar being exponential time worst case but in practice often closer to linear
- turminal 3y agoThe difference with SAT is that for SAT we actually know the opposite is true - the instances that can be solved quickly are the "rare" kind.
- isaacfrond 3y agoThe problem is that with probability 1 a random problem will access an undefined memory position. Such program halt by definition. This makes the result a lot less interesting. Sure random programs will typically halt before long, but with an illegal memory access ( in the parlance of the article, they read from the left of the turing tape)
- l33t233372 3y agoThere is no such notion of “undefined memory region” for a Turing Machine
- thelopa 3y agoSome models of the Turing machine have an infinite tape in only one direction. Some also don’t require every state to have an exhaustive set of transitions. Those models generally consider going off the end of the tape or failing to find a transition to be a halting state.
- l33t233372 3y agoIt’s unclear to me why restricting ourselves to that model is useful here
- knome 3y agoChanging the model wouldn't change anything. A turing machine is equivalent to any computational machine you want to put in there. It doesn't matter what the machine is. The turing machine is the goto because it was first used for them. Any other machine that can simulate a turing machine can simulate failing in those same ways. You can't escape the problems of turing completeness without losing it.
- mgraczyk 3y agoIt does matter, the second and last sentence of the abstract is "The proof is sensitive to the particular computational models."
- credit_guy 3y agoThis contradicts Murphy’s theorem, that if something can go bad it will go bad with asymptotic probability one.
- falcor84 3y agoWell, if the program is operating a business-critical function, then having it halt is bad.
- zeroonetwothree 3y agoI would say it’s consistent since something going bad can often mean halting
- klyrs 3y agoNo, Murphy says that despite having a vanishingly small probability, somebody will toss an undecidable problem into your non-halting oracle.
- l33t233372 3y agoI’ve never seen “asymptomatic density” referred to as “asymptomatic probability.” Anyways, if anyone is interested is a more complete survey of similarly flavored computability/density results, this paper is good: https://faculty.math.illinois.edu/~jockusch/DensityCE_JML.pdf https://faculty.math.illinois.edu/~jockusch/DensityCE_JML.pd... There is even some pure combinatorics involved, for example I remember lemma 6.7 from my combinatorics class back in undergrad
- meithecatte 3y agoNote: it's not asymptomatic, but asymptotic - without the ma. I can only wonder whether you've always been writing it like that, or if this is the toll that the pandemic had on you.
- aklein 3y agoMaybe they just need a vaccination… uh I mean a vacation
- l33t233372 3y agoI think my autocorrect got the better of me there!
- eterevsky 3y agoA few years ago I had an idea to try and solve halting problem for as many Brainfuck problems as possible, using a few simple heuristics. (To make things easier I picked a dialect with 1 byte cells that weren't allowed to over- or underflow.) I managed to solve all BF programs up to length 12. The longest running but stopping short program that I've found was this: >+[>++>+++[-<]>>], it stopped after 9212 steps. https://github.com/eterevsky/beaver https://github.com/eterevsky/beaver
- tromp 3y ago> I managed to solve all BF programs up to length 12. With 8 possible instructions, that is equivalent to all programs up to 12 * log 8 = 36 bits. Curiously, that exactly matches how far we were able to analyze the behaviour of a functional busy beaver [1]. > it stopped after 9212 steps. The largest output of a 36 bit lambda term is a whopping 578960446186580977117854925043439539266349923328202820197287920039565648199686 bits long though... [1] https://oeis.org/A333479 https://oeis.org/A333479
- smohare 3y ago[dead]
- saghm 3y agoFrom what I recall, the "undecidable" part of the halting problem isn't determining that something halts, but determining that it _doesn't_ halt (i.e. the halting problem is verifiable, as opposed to the inverse "non-halting" problem, which isn't verifiable, which is always the case for the inverse of a verifiable problem).\ I've never properly learned brainfuck, so the answer to this might be trivial without needing to write a solver, but what's the shortest non-halting program you found?
- shoo 3y agoThe shortest non-halting brainfuck program will have exactly three instructions. Here is one them: `+[]` here is another one: `-[]`. Brainfuck's state consists of an array of integers, an index into that array, a program counter, and some bookkeeping required to track which "[" corresponds to which "]". Let's assume the array a[:] is zeroed and the index i is set to 0 before the program begins executing. Then `+` increments the cell in the array a at index i, i.e. `a[i] += 1`; `[` begins a while loop, equivalent to `while a[i] != 0 {`; and `]` ends the while loop: `}` . So the program `+[]` is equivalent to something like a := (allocate a length N array of bytes, set to zero) i := 0 a[i] += 1 while a[i] != 0 { } which will not terminate. Why is this the shortest? `]` is the only instruction that might decrease the program counter, otherwise the program counter always increases by one or more. Therefore, a non-halting brainfuck program must include at least one `]`. Brainfuck programs are syntactically incorrect unless there is exactly one `]` occurring somewhere in the program after each `[`. So the shortest non-halting brainfuck program must have at least two instructions. There is only one syntactically valid brainfuck program with two instructions that might not halt: `[]`. But this will halt, assuming that the array `a` is initialised to zero before execution begins. So the shortest non-halting brainfuck program contains three instructions.
- tromp 3y agoThe meat of the paper is this short > Proof of the Main Theorem Using the standard model > let B be the set of programs that on input 0 either halt before repeating a state or fall off the tape before repeating a state. Clearly, B is polynomial time decidable, since we need only run a program p for at most n steps, where n is the number of states in p, to determine whether or not it is in B. It is equally clear that the halting problem is polynomial time decidable for programs p in B, since again we need only simulate p for n steps to know whether it halted or fell off. What remains is to prove that this behavior occurs with asymptotic probability one. The proof also makes use of this > Lemma 2.5 (Polya [2], see also, e.g., [1]) > In the random walk with equal likelihood of moving left or right on a semi-infinite tape, beginning on the left-most cell, the probability of eventually falling off the left edge is 1. This suggests that the result crucially depends on having a one-sided infinite tape rather than the two-sided infinite tape that's used in the Turing Machine busy beaver. It would be interesting to determine whether the result also holds for that other computational model, i.e. what about the set of lambda calculus terms with or without a normal form?
- calf 3y agoI got confused here: > Clearly, B is polynomial time decidable, since we need only run a program p for at most n steps, where n is the number of states in p, to determine whether or not it is in B. Couldn't program p have an exponential number of states, e.g. 2^|p| distinct program states? Then running the program for O(2^|p|) steps is clearly not polynomial time decidable in the size of the instance. I thought polynomial time, for the decision algorithm, meant O(|p|^c) for some c. Am I mistaken about something?
- tromp 3y agoIn this case p is the standard encoding of a Turing Machine with n states, so |p| = n * 2 * (1 + 1 + log(n+1)), so necessarily n < |p|.
- calf 3y agoYes thanks I figured that out later; they define the "state" as what in CS we would call the lines of code or control flow blocks. What I'm curious about is with our usual "modern programmer's" understanding of a state, the state space is exponential in the size of the program. That's why we have model checking and software verification. Whereas this theorem is about programs B whose state space is linear in the length of the encoding of the program, because they're allowed to visit each Turing machine state at most once before halting. At first glance seems like a very specialized case of a class of programs to talk about.
- jameshart 3y agoSimilarly, as the number of particles in a system increases, the less you have to worry about Heisenberg uncertainty bounds on your momentum/position measurements. It’s a misreading of the halting problem to think of it as a ‘barrier’ of some sort. What it really means is that there are some computer programs where the only way to find out what they will do is to actually run them. There’s not a ‘better trick’ you can pull to get the answer. This is kind of intuitive, since we know there are problems we run into where the easiest way we can think of to solve them is to write a program and run it. The halting problem tells us that it’s plausible that that instinct is right - that for some programs, you really can’t do some other analysis of the program that tells you what it’s going to do. You have to just run it. Like: take a random complex number with magnitude < 2. Keep squaring it and adding the original number. Will you ever get a number with magnitude > 2? For some numbers you can take a shortcut and say yes or no. But for others the only way to find out is to keep doing it.
- Y_Y 3y agoWhat does this have to do with Heisenberg uncertainty?
- mgraczyk 3y ago> The halting problem tells us that it’s plausible that that instinct is right - that for some programs, you really can’t do some other analysis of the program that tells you what it’s going to do. You have to just run it. This isn't quite right. The halting problem says that you can't just run it. If you just run it, you will not learn whether or not it halts after any finite amount of time. Also I don't see how this is related to uncertainty bounds.
- nico 3y agoIs there a contest somewhere for the longest continuously-running computation? It would be interesting to see how long we are capable of running even just a while true The power might go out, some electronic component might fail, or the cooling system, etc What is the longest that we are actually capable of keeping the most simple system running?
- jgtrosh 3y agoDoes the century old continuously running lamp bulb in a fire brigade count as a computation, if a while true does?
- mannykannot 3y agoLife on Earth is an out-of-equilibrium process that has been running for ~3.5 billion years.
- odo1242 3y agoProbably Voyager 2. Running since August 20, 1977 - never been rebooted (because good luck doing that)
- schoen 3y agoMaybe there's a clock on Earth with a microcontroller and some kind of UPS or battery backup or large capacitor backup? You could argue that the timekeeping of TAI (https://en.wikipedia.org/wiki/International_Atomic_Time https://en.wikipedia.org/wiki/International_Atomic_Time) could be seen as a distributed computation (where different entities are counting the same value and running manual and automated protocols to keep the value synchronized), and that has been running since 1972. It almost certainly hasn't been running continuously on any individual hardware device, but there have always been devices that represented its value and always been efforts to maintain continuity between calculations. Although I guess the same logic could argue for civil timekeeping in any calendar, because people have actively tracked it as "the same computation" and cared about it for centuries or millennia. Maybe the distinctive argument for TAI is that it's presumably been continually represented digitally in programmable computers since 1972.
- adamnemecek 3y agoNo one talks about the fact that the halting problem has been solved for linear bounded automata.
- russdill 3y agoBecause it's immediately obvious that for anything with a finite number of states determining if it runs forever is "trivial" as running it until it either repeats a state or halts which will always occur in finite time.
- adamnemecek 3y agoRight, why are there so few total languages then?
- reuben364 3y agoBRB, implementing a x86 interpreter with O(2^n) memory overhead.
- adamnemecek 3y agoThat's the brute force approach.
- reuben364 3y agoI guess the alternative is just bounding the number of instructions and proving inside or outside your language that it is sufficient for your program.
- adamnemecek 3y agoIndeed, that's what bounded means.
- 3y ago
- Jeff_Brown 3y agoIt's an interesting result, but the probability distribution seems to be doing a lot of the work. The distribution of programs a human is likely to encounter is very different from the set of all programs of length N uniformly distributed.
- Beltiras 3y agoI had an insight when learning about the Halting Problem. There is a class of programs for which the Halting Problem is solvable since you can use circuit analysis to see if well-formed loops halt. We should strive to write programs in that class since then we know that the execution, long as it may be, will yield a result.