Is it possible to have a Turing-complete language that can't possibly go into an infinite loop?

246 Views Asked by At

Does there exist a Turing-complete system that can never be programmed to go into an infinite loop?

For all I know about Turing machines, this should not be possible. An arbitrary Turing machine can go into an infinite loop, and a Turing-complete language should be able to emulate an arbitrary Turing machine, so it should be possible to make any Turing-complete system to loop infinitely.

However, some well-credentialed person has told me (with no further explanation) that this is not the case and that I completely misunderstand this entire thing.

So tell me -- is it possible to have a Turing-complete language that can't be made to loop infinitely? If it is, then could you give me an example?

1

There are 1 best solutions below

0
On

"Does there exist a Turing-complete system that can never be programmed to go into an infinite loop?"

  • no, each turing machine can be programmed to land to infinite loop. Please look at the Holding Problem.There we cannot decide whether program is going to finish or too run infinitelly.

Turing language does not exist, the machine does, and different machines do accept certain languages. Now Turing machine can accept even the regular languages but not all of regular languages are finite if that is what you asked for.