20
$\begingroup$

What would be the easiest way to show if a newly designed language is Turing complete or not? Simulating a Turing machine could be cumbersome; can it be inferred from certain characteristics? For example, if it has condition-controlled loops and allows basic arithmetic, would that be enough?

$\endgroup$

4 Answers 4

17
$\begingroup$

A language is Turing complete if and only if you can interpret a known Turing complete language in it

Lemma: If language A can run any program in language B and language B can simulate a Turing machine than language A is also Turing complete.

The most common targets, since they are easy to implement include:

  • Brainfuck is a very simple language with only 8 instructions making it very easy to implement.
  • Rule 110 A very simple cellular automata that is also Turing complete. Very easy to implement but a bit abstract.

If your language is not Turing complete that is not necessarily a problem

There are many advantages to non-Turing complete languages. It's often very nice to be able to prove if a program will halt which is impossible for Turing complete languages. Languages like regular expressions are widely used precisely because they are not Turing complete making them relatively "safe"

$\endgroup$
1
  • 1
    $\begingroup$ I’d add tag systems to the list. Swift has at least two known ways to build undecidable type systems: one using semigroups, and another using tag systems. $\endgroup$
    – Bbrk24
    May 16, 2023 at 20:56
12
$\begingroup$

The other answers are great, but my personal litmus test is this:

  • Does the language have an if statement?
  • Does the language have the equivalent of a while loop?

If it has both, it's most likely Turing-complete.

Note that some loops don't qualify; a foreach-type loop that only iterates over ranges is not enough, but a for loop in which you can modify the variables used in the loop condition is sufficient.

$\endgroup$
2
  • $\begingroup$ I assume recursive function calls can be used instead of a while-loop. $\endgroup$
    – Jonas
    Jul 23, 2023 at 11:27
  • $\begingroup$ @Jonas, yes absolutely. $\endgroup$ Jul 23, 2023 at 20:44
3
$\begingroup$

You can try to compile a simple Turing complete language (such as the esolang BF) to your language, and if you can define a semantically sound compiler, then your language is Turing complete.

$\endgroup$
5
  • 1
    $\begingroup$ What is a semantically sound compiler? $\endgroup$
    – mousetail
    May 16, 2023 at 18:05
  • $\begingroup$ @mousetail that it correctly interprets what the input language is supposed to mean. For instance, a compiler that generates a "hello world" output for whatever input is still a compiler, but does not correctly interpret the input $\endgroup$
    – ice1000
    May 16, 2023 at 20:21
  • $\begingroup$ C is not Turing complete (all types have finite sizeof, "memcpy object semantics" guarantees then that any type including pointers has only a finite number of values, etc.), still many Turing complete languages can be compiled to C. $\endgroup$
    – nikita
    May 17, 2023 at 0:38
  • $\begingroup$ @nikita are those compilers preserve all the semantics? If I have a language that consumes infinite resources, is this behavior correctly compiled to C? $\endgroup$
    – ice1000
    May 17, 2023 at 0:43
  • $\begingroup$ This depends on how you define the semantics. Take as an example a language that supports arbitrary-sized integers. Suppose the language is translated to C. When x + 1 is evaluated, the translated program can run out of memory. There are multiple ways to handle this: crash, deadlock, exponentially slow increment so that memory is never actually exhausted, etc. Whether this preserves the semantics depends on how exactly the semantics is defined. $\endgroup$
    – nikita
    May 17, 2023 at 1:01
2
$\begingroup$

Try implementing a Turing machine in it

If you can implement a Turing machine in your language (pretending you are running on a computer with infinite resources), then by definition your language is Turing complete. While, as stated in the question, it is cumbersome (and for that reason I’d point you to mousetail’s answer), it is a definite check.

$\endgroup$
5
  • $\begingroup$ "barring the restriction of finite resources" is not true. Any language which can't (theoretically) store infinite information is not Turing Complete. $\endgroup$ May 16, 2023 at 18:24
  • $\begingroup$ @RadvylfPrograms That’s what I meant by “barring”. No computer has infinite resources. I’ve clarified a bit $\endgroup$
    – Seggan
    May 16, 2023 at 18:25
  • 1
    $\begingroup$ Many languages do fail that test as they limit the size of the pointer type $\endgroup$
    – mousetail
    May 16, 2023 at 20:23
  • $\begingroup$ @mousetail then they are not Turing complete? $\endgroup$
    – Seggan
    May 16, 2023 at 22:10
  • $\begingroup$ I guess technically but for all practical purposes they are $\endgroup$
    – mousetail
    May 17, 2023 at 4:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .