This forum is closed to new posts due to low activity and a deluge of spam. It is kept online as a static historical record. If you want to read about or discuss esoteric programming languages, the Esolang wiki is the place to go. An archive of the forum is available.

Simple turing completeness (2)

1 Name: personak : 2011-05-24 03:37 ID:JvCNRt/M

I once read that a turing-complete language only needs to run forever. Would a language that only had a command l - C equivalent of while(true){} - technically be turing-complete?

2 Name: Ørjan : 2011-05-24 22:58 ID:DFXfsevM

No, if you heard it that way, it's simply wrong.

Turing-complete means, approximately, that your language can be used to do any computation that a Turing machine can, which includes any computation done by ordinary (and most esoteric) programming languages, or by any real computer we can build. Clearly while(true){} cannot do any computation, or at most one computation if you are being lenient.

What is true is that for ordinary programming languages, they must be able to run forever if they are going to have any chance of being Turing complete.

However there are even stranger, purely mathematical Turing complete formalisms for which even the concept of running is not really well defined. (I think the word problem for groups is one.) In that case for any method of checking what the result of the formalism is, that method must sometimes run forever.

Name: Link:
Leave these fields empty (spam trap):
More options...