3 ms·

> Undecidability requires infinities Not in any reasonably modern system. The state in this case is the exact sequence of bits contained in RAM and on your har

by chias 7y ago

> Undecidability requires infinities Not in any reasonably modern system. The state in this case is the exact sequence of bits contained in RAM and on your hard drive, which might as well be infinite (lets ignore for a moment that your computer is connected to the Internet and to real entropy sources, which really do make things infinite). Some napkin math: if you've got a terabyte hard drive and 32 gigs of RAM, then there are approximately 2^(1,032 * 1024 * 1024) states your computer might be in, which is about 1.79 * 10 ^ 325,753,719. It can be hard to conceptualize numbers at that scale, but a fun illustration is that it is so big that the number itself would not fit on many laptops. It is infinite for any useful sense. For comparison, there are an estimated 10^86 atoms in the observable universe -- if each atom in the universe was in fact its own universe, and each atom in all of those universes was its own universe, and so on... you'd have to go four layers deep to start talking comparable numbers here.

hollowcelery 7y ago
Computational and complexity theory are abstract mathematical subjects where numbers are either finite or infinite. A very large finite number is still finite. There is no meaningful notion of "so big that we can pretend it is infinity" in questions of decidability, and the limitations of the real world are irrelevant.
mannykannot 7y ago
A finite deterministic state machine can not perform more transitions than it has states without returning to a state it has been in before, and once that happens, because it is deterministic, it will repeat the sequence of transactions, that occurred between the first and second occurrence of that state, indefinitely. All programs that halt, therefore, must do so in less than #states steps, and the rest certainly never will, so we could show, in finite time, whether any given program on that machine will halt. We know, therefore, that the halting problem on this machine is decidable, even if we could not, in practice, demonstrate it. The halting problem was not posed because we want to know if a given program will halt; it was posed as a means of attacking a much deeper problem. Note also that any NFA can be converted to an equivalent DFA by powerset construction. https://en.wikipedia.org/wiki/Powerset_construction https://en.wikipedia.org/wiki/Powerset_construction

by chias 7y ago

hollowcelery 7y ago

Computational and complexity theory are abstract mathematical subjects where numbers are either finite or infinite. A very large finite number is still finite. There is no meaningful notion of "so big that we can pretend it is infinity" in questions of decidability, and the limitations of the real world are irrelevant.

mannykannot 7y ago

A finite deterministic state machine can not perform more transitions than it has states without returning to a state it has been in before, and once that happens, because it is deterministic, it will repeat the sequence of transactions, that occurred between the first and second occurrence of that state, indefinitely. All programs that halt, therefore, must do so in less than #states steps, and the rest certainly never will, so we could show, in finite time, whether any given program on that machine will halt. We know, therefore, that the halting problem on this machine is decidable, even if we could not, in practice, demonstrate it. The halting problem was not posed because we want to know if a given program will halt; it was posed as a means of attacking a much deeper problem. Note also that any NFA can be converted to an equivalent DFA by powerset construction. https://en.wikipedia.org/wiki/Powerset_construction https://en.wikipedia.org/wiki/Powerset_construction