Hacker News new | ask | show | jobs
by ProfHewitt 2497 days ago
Digital arbiters can theoretically take an arbitrary amount of time to settle although statistically they tend to settle soon rather than later. Also, if an Actor sends itself a 'stop' message over the Internet via Timbuktu, it can take an arbitrary amount of time to be received back. Also, an Actor can take an arbitrary amount of time to process a message.

In the above models of computation, arbitrary means absolutely arbitrary, i.e., there is no a priori bound on the amount of time that it can take.

Your trouble may be with Plotkin's proof, which shows that state machine models of nondeterministic computation are inadequate.

1 comments

I have no problem with the proof. It's easy to come up with non-computable abstractions. All of calculus is one (in fact, Turing himself pointed it out in "On Computable Numbers", and he invented and used others when he found them useful), yet it's commonly used to model natural systems without anyone considering it a proof against Church-Turing. So the fact that an abstraction is non-computable is unsurprising and has nothing to do with the thesis. The Turing thesis is relevant when you're talking about a physical realization, and you have not provided any proof that you've found one that's not Turing-computable.

Every physical object does have an a priori bound on the amount of time it can take to do something, unless that time could possibly be infinite. The reason is that it needs some sort of a counter, so it needs some state, and there's only so much state storable in the universe to store a counter.