3 ms·
No actual real real world computer is Turing complete. Only the. A problem is computable if it can be expressed in such a way that a Turing machine can solve
by nabla9 8y ago
No actual real real world computer is Turing complete. Only the. A problem is computable if it can be expressed in such a way that a Turing machine can solve it. That's theoretical result. The set of computable problems is not the set of problems that real world computers (or humans) can solve in some finite time and space.
Any problem that any human in history has ever solved could have been solved with finite state machine of sufficient size.
- skdotdan 8y agoIn practice, computers and many programming languages are considered Turing complete because arbitrary (yet finite, obviously) amounts of memory can be added if needed. Eg. Java is considered Turing complete even if no JVM instance will ever be able to have access to infinite memory. Theoretically, you are right. But does strict Turing completeness matter, in practice? I don't have the required knowledge to counter-argument your last point.
- nabla9 8y agoIf we consider the context of argument I feel that I was more on the point and you were sidetracked. This is the context that was set up by user yters > E.g. how could we possible write functioning code so consistently if we are limited by the halting problem for Turing machines? You can't use known limits of Turing machines to argue that humans can do better because we can't.
- skdotdan 8y agoSorry, that's right.