6 ms·

Well yeah, all modern computers and software are nondeterministic state machines. The order and set of operations is nondeterministic, and its input, output and

Well yeah, all modern computers and software are nondeterministic state machines. The order and set of operations is nondeterministic, and its input, output and algorithm constantly mutates. As there is no function within the computer to automatically reverse its tree of operations to before it encountered a conflict, an infinite number of state changes inevitably leads to entropy, thus all running systems [with state changes] crash. Since the computer is a state machine, and all initial state is read from disk, restarting the computer reinitializes the state machine from initial state. Rebooting resets the state machine to before state mutation entropy led to conflicts. Rebooting is state machine time travel. We could prevent this situation by designing systems whose state and algorithms don't mutate. But that would require changing software development culture, and that's a much harder problem than rebooting.

legalcorrection 4y ago
It is 100% theoretically possible to build a complex system that never enters an invalid state. But because human beings are fallible—and attempts to correct that infallibility are not just expensive, but themselves subject to further fallibility—no such complex system will ever be built.
- mkleczek 4y ago
  Actually building such a computer is provably impossible: https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem I highly recommend this talk on the subject: https://pron.github.io/posts/correctness-and-complexity https://pron.github.io/posts/correctness-and-complexity
  - legalcorrection 4y ago
    Rice’s theorem says no such thing. Rice’s theorem tells you you can’t necessarily prove you’ve built a flawless system, not that you can’t build a flawless system. You can build a perfect program even if you can’t necessarily then know you have. Perhaps you interpreted my post to suggest that you could build a machine that verifies that any arbitrary software run on it never enters an invalid state? If so, I agree, that is not possible. I made a minor edit to make it clear what I’m talking about.
    - mkleczek 4y ago
      > Rice’s theorem tells you you can’t prove you’ve built a flawless system, not that you can’t build a flawless system. If you think about it - it is the same: how do you know the system you just built is flawless?
      - ncmncm 4y ago
        Because you built it in a series of steps, exactly zero of which introduced any undecidability.
        mkleczek 4y ago
        See above - there is no reliable procedure (algorithm) that would allow you to build a TM with arbitrary properties (ie. implementing arbitrary requirements).
        SAI_Peregrinus 4y ago
        Programs don't have to have Turing-complete behavior. Compilers do, but not every program needs to implement uncomputable behavior on its inputs.
        mkleczek 4y ago
        Actually it's the other way around: In reality most interesting programs accept Turing complete languages - albeit not formally specified :)
      - legalcorrection 4y ago
        You don't, but it's still flawless. My point was that it was theoretically, not practically possible. So your retort that it's not practically possible is kind of missing the point.
        mkleczek 4y ago
  - librexpr 4y ago
    Rice's Theorem isn't as strong as you say it is. What it says is that there exist programs that it's impossible to prove whether or not they have specific non-trivial properties. But there still exist many programs where we can prove their correctness / incorrectness. What's more, I'd argue that if you're writing code whose behaviour is literally undecidable, you're doing something wrong, unless you're doing it for research purposes or something like that.
    - mkleczek 4y ago
      > Rice's Theorem isn't as strong as you say it is It is very strong: its corollary is there is no general algorithm to build Turing Machines with arbitrary non-trivial properties (if there was such an algorithm we could use it to build a TM that solves the halting problem) So for any non-trivial property the only way to build a TM with this property is to use some ad-hoc method (as there is no general algorithm) - but how do we know the TM we've just built really holds the property we wanted it to? There is no way to verify it due to Rice's theorem.
      - feanaro 4y ago
        This still doesn't exclude the existence of a general method for a well-behaved subset of Turing machines. It is the model of Turing machines that is too powerful.
        mkleczek 4y ago
        There are two problems with this: 1. Even for as weak computational model as FSM the problem of verifying its correctness is intractable (NP-hard). And modularisation does not help. 2. We don't know any weaker computational model that is strong enough to be viable for the problems we want to solve and still weaker than TM. It is well known that it is surprisingly easy for a language to be (accidentally) Turing complete.
        ncmncm 4y ago
        It is not necessary to verify that random presented machines have some property. It suffices that we can reliably construct machines that perform a desired function and have the desired property.
- beckingz 4y ago
  Physical things fail or have failure done to them. You make a big claim.
  - legalcorrection 4y ago
    Good point. I’m putting aside the physical nature of the machine that must ultimately run the software. Made a minor edit so I’m talking about a “system” not a “machine”.
- 0xbadcafebee 4y ago
  State machines can already deal with invalid state. They can walk a tree of operations/input until they hit a "dead end" and then go back up the tree and try other operations. But you don't need to entirely remove the possibility of invalid state. You can add mitigations. One mitigation is regularly snapshotting state, and on error allow the user to revert to a previous state. Your browser's Back button is a form of this. Another is programmed responses to invalid state. If the program encounters an invalid state, it can attempt to resolve the issue. One method would be to bubble up a signal to the system, and the system can have pre-programmed responses. For example, if a program raises an exception of "Error: Out of disk space", then the larger system can be triggered to perform some disk space garbage collection. If a program raises an "Out of memory" error, the Linux kernel already has an "Out of memory killer" that attempts to relieve applications of their memory. We can come up with much more sophisticated methods if we try. But again, this would require software development culture to think outside the box, and that is highly unlikely.

legalcorrection 4y ago

It is 100% theoretically possible to build a complex system that never enters an invalid state. But because human beings are fallible—and attempts to correct that infallibility are not just expensive, but themselves subject to further fallibility—no such complex system will ever be built.

mkleczek 4y ago
Actually building such a computer is provably impossible: https://en.wikipedia.org/wiki/Rice%27s_theorem https://en.wikipedia.org/wiki/Rice%27s_theorem I highly recommend this talk on the subject: https://pron.github.io/posts/correctness-and-complexity https://pron.github.io/posts/correctness-and-complexity
- legalcorrection 4y ago
  Rice’s theorem says no such thing. Rice’s theorem tells you you can’t necessarily prove you’ve built a flawless system, not that you can’t build a flawless system. You can build a perfect program even if you can’t necessarily then know you have. Perhaps you interpreted my post to suggest that you could build a machine that verifies that any arbitrary software run on it never enters an invalid state? If so, I agree, that is not possible. I made a minor edit to make it clear what I’m talking about.
  - mkleczek 4y ago
    > Rice’s theorem tells you you can’t prove you’ve built a flawless system, not that you can’t build a flawless system. If you think about it - it is the same: how do you know the system you just built is flawless?
    - ncmncm 4y ago
      Because you built it in a series of steps, exactly zero of which introduced any undecidability.
      - mkleczek 4y ago
        See above - there is no reliable procedure (algorithm) that would allow you to build a TM with arbitrary properties (ie. implementing arbitrary requirements).
        SAI_Peregrinus 4y ago
        Programs don't have to have Turing-complete behavior. Compilers do, but not every program needs to implement uncomputable behavior on its inputs.
        mkleczek 4y ago
        Actually it's the other way around: In reality most interesting programs accept Turing complete languages - albeit not formally specified :)
    - legalcorrection 4y ago
      You don't, but it's still flawless. My point was that it was theoretically, not practically possible. So your retort that it's not practically possible is kind of missing the point.
      - mkleczek 4y ago
- librexpr 4y ago
  Rice's Theorem isn't as strong as you say it is. What it says is that there exist programs that it's impossible to prove whether or not they have specific non-trivial properties. But there still exist many programs where we can prove their correctness / incorrectness. What's more, I'd argue that if you're writing code whose behaviour is literally undecidable, you're doing something wrong, unless you're doing it for research purposes or something like that.
  - mkleczek 4y ago
    > Rice's Theorem isn't as strong as you say it is It is very strong: its corollary is there is no general algorithm to build Turing Machines with arbitrary non-trivial properties (if there was such an algorithm we could use it to build a TM that solves the halting problem) So for any non-trivial property the only way to build a TM with this property is to use some ad-hoc method (as there is no general algorithm) - but how do we know the TM we've just built really holds the property we wanted it to? There is no way to verify it due to Rice's theorem.
    - feanaro 4y ago
      This still doesn't exclude the existence of a general method for a well-behaved subset of Turing machines. It is the model of Turing machines that is too powerful.
      - mkleczek 4y ago
        There are two problems with this: 1. Even for as weak computational model as FSM the problem of verifying its correctness is intractable (NP-hard). And modularisation does not help. 2. We don't know any weaker computational model that is strong enough to be viable for the problems we want to solve and still weaker than TM. It is well known that it is surprisingly easy for a language to be (accidentally) Turing complete.
        ncmncm 4y ago
        It is not necessary to verify that random presented machines have some property. It suffices that we can reliably construct machines that perform a desired function and have the desired property.
beckingz 4y ago
Physical things fail or have failure done to them. You make a big claim.
- legalcorrection 4y ago
  Good point. I’m putting aside the physical nature of the machine that must ultimately run the software. Made a minor edit so I’m talking about a “system” not a “machine”.
0xbadcafebee 4y ago
State machines can already deal with invalid state. They can walk a tree of operations/input until they hit a "dead end" and then go back up the tree and try other operations. But you don't need to entirely remove the possibility of invalid state. You can add mitigations. One mitigation is regularly snapshotting state, and on error allow the user to revert to a previous state. Your browser's Back button is a form of this. Another is programmed responses to invalid state. If the program encounters an invalid state, it can attempt to resolve the issue. One method would be to bubble up a signal to the system, and the system can have pre-programmed responses. For example, if a program raises an exception of "Error: Out of disk space", then the larger system can be triggered to perform some disk space garbage collection. If a program raises an "Out of memory" error, the Linux kernel already has an "Out of memory killer" that attempts to relieve applications of their memory. We can come up with much more sophisticated methods if we try. But again, this would require software development culture to think outside the box, and that is highly unlikely.