Meta Turing-complete

From Esolang
(Redirected from Meta turing-complete)
Jump to navigation Jump to search

A language can be said to be meta Turing-complete if it is able to describe a Turing-complete language.

Meta Turing-completeness vs Turing-completeness

It is possible to make the argument that, because all meta Turing-complete languages are able to describe (implement or compile) a Turing-complete language, they are also Turing-complete. However, a meta Turing-complete language does not necessarily allow an arbitrary effect at an arbitrary point. They simply need to be able to describe a Turing-complete language, which does not imply that they are able to control their input, or able to execute commands independently. If a meta Turing-complete language is combined with some input, it is a Turing-complete language.

A Turing-complete language is necessarily meta Turing-complete: it is able to interpret (describe) another Turing-complete language.

Input/Output

While meta-languages sometimes have input/output (the code to compile/the compiled code or the code to interpret/the interpreted code), it is not necessary for meta Turing-completeness; like Turing-completeness, the definition of meta Turing-completeness does not prevent anyone from setting up a starting memory-area and/or reading from the finished memory.

The physical world

It is not possible to implement a meta Turing-complete language in the real world, because it would require an implementation of a Turing-complete language, which is impossible.

Relationship to esoteric programming

Some of the esoteric languages are meta-languages; they describe other languages. If those languages are able to describe a Turing-complete language, they are meta Turing-complete. An example of a meta Turing-complete language is ALPACA: it is able to describe Conway's Game of Life, which is a Turing-complete cellular automaton.