7 ms·
Arguments that claim something is impossible from an argument related to the halting problem are generally bogus. The halting problem applies only to determinis
by Animats 6y ago
Arguments that claim something is impossible from an argument related to the halting problem are generally bogus. The halting problem applies only to deterministic systems with infinite state. If you have finite state and determinism, you have to eventually repeat a state, or halt. Note that "very large" and "infinite" are not the same thing here.
Not being able to predict something for combinatorial or noise reasons is a more credible argument.
- ben_w 6y agoDifferent for pure mathematics sure, but is that of practical importance given how fast busy-beaver numbers grow?
- uyt 6y agoI don't understand the busy beaver stuff, but is this argument similar: On a 32-bit computer, there are 2^32 bytes of memory or 256^(2^32)=2^34359738368 possible states. A program is something that takes you from one memory state to another and you want to figure out if the state transitions form a cycle?
- ben_w 6y agoSimilar idea, but with Turing machines rather than physical computers. Simplified a bit, the n-th busy beaver number is the number of 1s which can be written out by an n-state Turing machine. For 2-symbols and n-states, the sequence goes: 6, 21, 107, >= 47176870, > 7.4×10^36534, > 10^10^10^10^18705353 — and those inequalities are because the numbers themselves cannot be computed directly, you have to run the program to see what it does. https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver
- dvdkhlng 6y agoI think this approach quickly enters the realm of transcomputational problems [1], which, given the limits of this universe is equivalent to "undecidable" for all practical considerations. [1] https://en.wikipedia.org/wiki/Transcomputational_problem https://en.wikipedia.org/wiki/Transcomputational_problem
- Retric 6y agoBusy-beaver only grows fast given unlimited memory. On a finite machine it’s limited by the total number of states the device has. Granted that can be 10^1,000,000,000,000+ these days, but it’s still limited so BB(10^10) on actual hardware = BB(10^100).
- red75prime 6y agoIf you somehow know BB numbers, you know the size of finite memory, which is sufficient to run corresponding busy-beaver. Limiting mathematics to what is physically possible is not useful. We don't know what is ultimately physically possible.
- adrianN 6y agoWe have some upper bounds on what is physically possible: https://arxiv.org/abs/quant-ph/9908043 https://arxiv.org/abs/quant-ph/9908043
- jonathanstrange 6y agoWait a minute, does this paper include various hypercomputers or is it only about conventional computation? Although I personally believe hypercomputers are not physically possible, I'm not aware of any general proof that they are physically impossible. I've seen papers that suggest physical models for hypercomputers. Notice that there is a hierarchy of hypercomputers of varying powers and some of them can solve the Halting Problem.
- adrianN 6y agoThe paper includes quantum computers, it does not include computers that exploit CTCs or similar things whose existence we can only speculate upon. Note however that CTCs don't give you hypercomputation. Do you have a link discussing physical models for hypercomputers?
- jonathanstrange 6y ago
- im3w1l 6y agoBusy beavers have an infinite tape to work with, so that's a pretty big difference.
- djkndjn 6y agowhat you need to understand about the halting problem is that at is core it is an epistemological problem. An other expresion of it are Gödel's incompleteness theorems. Imagine a blank sheet of paper the area of the paper is what is knowable now start building logic as a data structure. We start with the first nodes which are the axioms now everything derived conects to other nodes etc as it expands as mold its going to cover some of the paper but wont be able to cover all. So the danger here is that computers are living on that fractal dimension and will never be able to see outside of it but us human beings have as kurt said intuition. The fact that we can find this paradoxes in logic means that our brains operate on a higher dimension and that computers will allways have blind spots.
- michaelmrose 6y agoYou need to start by proving that brains and all idealized computers we can build are inherently on different levels. Intuitively it seems like intuition is just a probabilistic analysis on incomplete data. For example that shadow is "probably" a predator that may eat me or that sound is probably a prey animal I can kill and eat. Current AI which probably doesn't fit either of our definitions of intelligence can design novel untrained strategies. See for example AlphaGo Zero. It's not even clear exactly how our brains work so its hard to imagine that they couldn't be implemented with a sufficiently powerful computer but more broadly a computer doesn't necessarily mean a silicon chip any more than it meant a vacuum tube. If silicon chips prove an insufficient mechanism there is no particular reason we couldn't somehow use a biological substrate or indeed even one we haven't thought of. Perhaps you simply need to acknowledge our limited understanding of the brain AND expand your definition of the term computer.
- happythomist 6y ago> It's not even clear exactly how our brains work so its hard to imagine that they couldn't be implemented with a sufficiently powerful computer... Not commenting on what OP said, but I don't think this is correct. Even in principle, how can any computational process produce conscious experiences, which are by nature subjective and unquantifiable?
- westoncb 6y agoIs this the case just because it's common for these arguments to be structured as contradiction proofs? Since contradiction proofs are arguments that operate in connection with the structure of proofs in general rather than exclusively in terms of the specific problem, then the entire argument may collapse on a technicality like "very large" vs "infinite". It's almost like the truth status of the argument is sharply discontinuous: you can't modulate the argument slightly and arrive at sensibly related assertions. Whereas if the argument were made solely in terms of the problem itself (without the added meta-layer argument from the contradiction proof), but still used the halting problem, then we might consider the fact that in reality our computers have finite state so are technically exempt, but the argument still holds for all intents and purposes because of how large the finite state is. Or is there another reason these arguments are generally bogus?
- AnHonestComment 6y agoYou actually noticed something deeper than your original question — “continuity of logic”, in the sense of “continuous function”. If you imagine you have a lot of inputs to a predicate, then the topology of their truthiness tells you something — and we can talk about “smooth” logic models, where being a little wrong in our assumption means we’re a little wrong in our conclusion. We can then apply tools from analysis, like bifurcation theory. The “halting problem schema” has a bifurcation at the finite/infinite boundary, which isn’t particularly uncommon for high level functions. But it’s important to know, when writing proofs. And generally speaking, places bifurcations can happen are regimes where your model is going to struggle. In the business world, knowing the “logic faults” of your model and keeping yourself in a “smooth regime” is important.
- blonde_ocean 6y agoHow else do you prove something using the halting problem other than a proof of contradiction?
- voxl 6y agoYou're missing the point. First, even with determinism and finite state, to witness the repeated state for any arbitrary program would require a meta machine with _more_ memory then the running machine. That's the ultimate problem, internally you can't notice if you're going to terminate, and a machine of the same power can't either. It's gotta be stronger.