News for hackers. Stuff that matters.

A comment on On rebooting: the unreasonable effectiveness of turning computers off and on. Parent comment

Re:On rebooting: the unreasonable effectiveness of turning c... by ncmncm on Wednesday May 25, 2022 @04:56AM (#31502037)
Making a system Turing-complete, even accidentally, does not make it proof against analysis. A system or input for the system may be built out of parts that could be used to make an undecidable system. But that does not mean you can only build undecidable systems with those parts.

It is in fact extremely common to build wholly deterministic machines out of the same parts as our unreliable computers, that are correct by construction. And they may implement a Turing-complete language and still be wholly deterministic, just by limiting the input to what can be proven deterministic in a strictly limited time. Again, this is normally by construction, where the proof is always trivial.

Such a proven-correct system can model literally any space-constrained algorithm.

[ Parent | on HN ]
Re:On rebooting: the unreasonable effectiveness of turning c... by mkleczek on Wednesday May 25, 2022 @05:38AM (#31502284)
> It is in fact extremely common to build wholly deterministic machines out of the same parts as our unreliable computers, that are correct by construction.

It is neither common nor easy but actually provably impossible. Please read this piece carefully: https://pron.github.io/posts/correctness-and-complexity

[ Parent | on HN ]
Re:On rebooting: the unreasonable effectiveness of turning c... by ncmncm on Wednesday May 25, 2022 @06:42AM (#31502629)
Yet, it is done, thousands of times every day, all over the world.

You must be misunderstanding the work if you believe that what is being done routinely is impossible.

[ Parent | on HN ]
Re:On rebooting: the unreasonable effectiveness of turning c... by mkleczek on Wednesday May 25, 2022 @07:03AM (#31502777)
> You must be misunderstanding the work if you believe that what is being done routinely is impossible.

Quite possibly I don't understand what you mean by "work". If by "work" you mean creating provably correct software then no, it is not done routinely.

[ Parent | on HN ]
Re:On rebooting: the unreasonable effectiveness of turning c... by ncmncm on Wednesday May 25, 2022 @07:27AM (#31502988)
The work is the paper you cited.

People create wholly deterministic state machines all the damn time.

[ Parent | on HN ]
Re:On rebooting: the unreasonable effectiveness of turning c... by mkleczek on Wednesday May 25, 2022 @07:50AM (#31503198)
> People create wholly deterministic state machines all the damn time.

What do you mean by "wholly deterministic"?

[ Parent | on HN ]
Re:On rebooting: the unreasonable effectiveness of turning c... by ncmncm on Wednesday May 25, 2022 @01:44PM (#31507918)
All possible states are well-understood, all possible paths through states are mapped.

You can buy an 8-bit adder/accumulator from a catalog.

[ Parent | on HN ]