2 ms·
That's redefining the problem—if you add a timeout, you are explicitly making the language not Turing complete any more.
by klodolph 9y ago
That's redefining the problem—if you add a timeout, you are explicitly making the language not Turing complete any more.
- icebraining 9y agoThe language still is, just not the environment in which it runs. Much like a language can be Turing-complete without having infinite tape/memory to run on.
- klodolph 9y agoWhen people say "Turing-complete" it's usually assumed that we are talking about computational models which could emulate Turing machines given infinite memory. But we don't have infinite memory. Adding time limits radically changes things.