<p>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?</p>

<computability>
How can I check if a new language is Turing-complete?
<p>The other answers are great, but my personal litmus test is this:</p>
<ul>
<li>Does the language have an <code>if</code> statement?</li>
<li>Does the language have the equivalent of a <code>while</code> loop?</li>
</ul>
<p>If it has both, it's most likely Turing-complete.</p>
<p>Note that some loops don't qualify; a <code>foreach</code>-type loop that only iterates over ranges is not enough, but a <code>for</code> loop in which you can modify the variables used in the loop condition <em>is</em> sufficient.</p>

CC BY-SA 4.0
2023-05-16T20:34:21.893Z
2023-05-16T20:34:21.893Z
Gavin D. Howard
CC BY-SA 4.0
2023-07-23T11:27:48.990Z
I assume recursive function calls can be used instead of a `while`-loop.
Jonas
CC BY-SA 4.0
2023-07-23T20:44:30.227Z
@Jonas, yes absolutely.
Gavin D. Howard
<h1>Try implementing a Turing machine in it</h1>
<p>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.</p>

CC BY-SA 4.0
2023-05-16T17:42:31.910Z
2023-05-16T18:26:30.030Z
2023-05-16T18:26:30.030Z
Seggan
CC BY-SA 4.0
2023-05-16T18:24:32.133Z
"barring the restriction of finite resources" is not true. Any language which can't (theoretically) store infinite information is not Turing Complete.
rydwolf
CC BY-SA 4.0
2023-05-16T18:25:12.880Z
@RadvylfPrograms That’s what I meant by “barring”. No computer has infinite resources. I’ve clarified a bit
Seggan
CC BY-SA 4.0
2023-05-16T20:23:32.810Z
Many languages do fail that test as they limit the size of the pointer type
mousetail 'he-him'
CC BY-SA 4.0
2023-05-16T22:10:25.843Z
@mousetail then they are not Turing complete?
Seggan
CC BY-SA 4.0
2023-05-17T04:35:52.257Z
I guess technically but for all practical purposes they are
mousetail 'he-him'
<p>You can try to compile a simple Turing complete language (such as the esolang <a href="https://esolangs.org/wiki/Brainfuck" rel="nofollow noreferrer">BF</a>) to your language, and if you can define a semantically sound compiler, then your language is Turing complete.</p>

CC BY-SA 4.0
2023-05-16T17:50:38.653Z
2023-05-16T17:50:38.653Z
ice1000
CC BY-SA 4.0
2023-05-16T18:05:00.420Z
What is a semantically sound compiler?
mousetail 'he-him'
CC BY-SA 4.0
2023-05-16T20:21:04.857Z
@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
ice1000
CC BY-SA 4.0
2023-05-17T00:38:31.593Z
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.
nikita
CC BY-SA 4.0
2023-05-17T00:43:36.687Z
@nikita are those compilers preserve all the semantics? If I have a language that consumes infinite resources, is this behavior correctly compiled to C?
ice1000
CC BY-SA 4.0
2023-05-17T01:01:05.680Z
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.
nikita
<p>I found this list of required constructs relatively useful (from a Robert C. Martin video):</p>
<ol>
<li>Input</li>
<li>Output</li>
<li>Memory</li>
<li>Logic</li>
<li>Control</li>
</ol>
<p>1 and 2 not strictly needed, but if there's no &quot;programming&quot; from the outside (therefore more like hard-wired?) and no computed results reported back, one may wonder why program and compute something in the first place.</p>
<p>3 might not be needed for a purely functional language, but the programs and results likely need to be stored somewhere and not all come from and go to I/O only. I mean, it's important for a Turing machine to produce, store and execute new programs generated by programs that currently run, in order to get some meta-circular, &quot;self-modifying&quot; benefits from the machine.</p>
<p>4 does not need to just be &quot;arithmetic&quot;, or basically that's just comparisons to make for a conditional, all of which can be synthesized from most primitive binary comparisons of the two input operands of a transistor (not useful/efficient though).</p>
<p>5 flow control is the (conditional) jump, the result of the comparison from 4 goes into it as jump condition. It may be inevitable that the jump is branching &quot;by some method&quot;, to have a &quot;then&quot;- and &quot;else&quot; branch to jump to based on whether or not a prior logic result as the condition is true. Loops can be produced from jumps. Notice, the results from 4 logic/arithmetic/other operations steer/control the further operation of the machine, constituting a software program that can be somewhat dynamic, which goes beyond fixed machine control.</p>
<p>It may be sufficient to check for the presence of these constructs/features, no matter how cumbersome or inefficient, as this allows for the most primitive stage of what's required for a &quot;programmable&quot; machine (and a language that's sufficient to program such per meta-circular software development, in the Turing sense of &quot;computer&quot; in contrast to other controlled machinery).</p>
<p>One typical test/indicator is if an interpreter/compiler for the language can be programmed in the language, because that's kind of proof that the required parts are there for software-modifyability (writing software by using software) and also executing it, which involves the same constructs that are needed for other programs (as these too deal with the same 1-5).</p>
<p>Or otherwise, if your language satisfies these minimal requirements, any other program (as a description-of/solution-to a problem) that may be written in some other language might as well be written in yours, however crude (like, if you had to synthesize numerical arithmetic from binary comparisons you store and pull back from memory, calculating memory addresses in your virtual or physical stack by the same method, implementing the &quot;next&quot; counter and its jumps to new addresses where there's new instructions by the same method, dispatching your instruction set to implementations by the same method, the implementation being constructed by the same method, etc.).</p>
<p>There's very primitive &quot;environments&quot; which were proven to be Turing complete, for example Conway's Game of Life (not really having convenient 4 logic nor 5 control and instead needs to be made up for with clever patterns) or XSLT (not really having 3 memory, version 1.0 less so, newer versions maybe more so, but passing arguments to parameterizable templates does act as memory of a crude kind), while other types of languages like some query languages (SQL comes to mind, only newer features may push it too towards Turing completeness) or markup languages, lack some of these required criteria. So if your language covers 1-5 in some form, it pretty likely is Turing complete, given less has been proven to be. From there, it mostly becomes a question of usage convenience and execution efficiency, vs. the formal proof of Turing completeness.</p>

CC BY-SA 4.0
2024-06-12T22:10:53.130Z
2024-06-14T22:24:56.230Z
2024-06-14T22:24:56.230Z
skreutzer
<h2>A language is Turing complete if and only if you can interpret a known Turing complete language in it</h2>
<p>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.</p>
<p>The most common targets, since they are easy to implement include:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Brainfuck" rel="noreferrer">Brainfuck</a> is a very simple language with only 8 instructions making it very easy to implement.</li>
<li><a href="https://en.wikipedia.org/wiki/Rule_110" rel="noreferrer">Rule 110</a> A very simple cellular automata that is also Turing complete. Very easy to implement but a bit abstract.</li>
</ul>
<h3>If your language is not Turing complete that is not necessarily a problem</h3>
<p>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 &quot;safe&quot;</p>

CC BY-SA 4.0
2023-05-16T17:39:40.417Z
2023-05-16T20:43:54.073Z
2023-05-16T20:43:54.073Z
mousetail 'he-him'
CC BY-SA 4.0
2023-05-16T20:56:42.540Z
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.
Bbrk24
# How can I check if a new language is Turing-complete?
Posted by: username_0 on 2023-05-16
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?
**Tags:** computability
---
## 5 answers
### Answer by username_5 on 2023-05-16. Score: 21 | Accepted answer
## 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](https://en.wikipedia.org/wiki/Brainfuck) is a very simple language with only 8 instructions making it very easy to implement.
* [Rule 110](https://en.wikipedia.org/wiki/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"
> **Comments:**
> **username_9** (2023-05-16): 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.  
---
### Answer by username_1 on 2023-05-16. Score: 15
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.
> **Comments:**
> **username_2** (2023-07-23): I assume recursive function calls can be used instead of a `while`-loop.  
> **username_1** (2023-07-23): @Jonas, yes absolutely.  
---
### Answer by username_3 on 2023-05-16. Score: 4
# 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.
> **Comments:**
> **username_4** (2023-05-16): "barring the restriction of finite resources" is not true. Any language which can't (theoretically) store infinite information is not Turing Complete.  
> **username_3** (2023-05-16): @RadvylfPrograms That’s what I meant by “barring”. No computer has infinite resources. I’ve clarified a bit  
> **username_5** (2023-05-16): Many languages do fail that test as they limit the size of the pointer type  
> **username_3** (2023-05-16): @mousetail then they are not Turing complete?  
> **username_5** (2023-05-17): I guess technically but for all practical purposes they are  
---
### Answer by username_6 on 2023-05-16. Score: 4
You can try to compile a simple Turing complete language (such as the esolang [BF](https://esolangs.org/wiki/Brainfuck)) to your language, and if you can define a semantically sound compiler, then your language is Turing complete.
> **Comments:**
> **username_5** (2023-05-16): What is a semantically sound compiler?  
> **username_6** (2023-05-16): @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  
> **username_7** (2023-05-17): 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.  
> **username_6** (2023-05-17): @nikita are those compilers preserve all the semantics? If I have a language that consumes infinite resources, is this behavior correctly compiled to C?  
> **username_7** (2023-05-17): 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.  
---
### Answer by username_8 on 2024-06-12. Score: -2
I found this list of required constructs relatively useful (from a Robert C. Martin video):

1. Input
2. Output
3. Memory
4. Logic
5. Control

1 and 2 not strictly needed, but if there's no "programming" from the outside (therefore more like hard-wired?) and no computed results reported back, one may wonder why program and compute something in the first place.

3 might not be needed for a purely functional language, but the programs and results likely need to be stored somewhere and not all come from and go to I/O only. I mean, it's important for a Turing machine to produce, store and execute new programs generated by programs that currently run, in order to get some meta-circular, "self-modifying" benefits from the machine.

4 does not need to just be "arithmetic", or basically that's just comparisons to make for a conditional, all of which can be synthesized from most primitive binary comparisons of the two input operands of a transistor (not useful/efficient though).

5 flow control is the (conditional) jump, the result of the comparison from 4 goes into it as jump condition. It may be inevitable that the jump is branching "by some method", to have a "then"- and "else" branch to jump to based on whether or not a prior logic result as the condition is true. Loops can be produced from jumps. Notice, the results from 4 logic/arithmetic/other operations steer/control the further operation of the machine, constituting a software program that can be somewhat dynamic, which goes beyond fixed machine control.

It may be sufficient to check for the presence of these constructs/features, no matter how cumbersome or inefficient, as this allows for the most primitive stage of what's required for a "programmable" machine (and a language that's sufficient to program such per meta-circular software development, in the Turing sense of "computer" in contrast to other controlled machinery).

One typical test/indicator is if an interpreter/compiler for the language can be programmed in the language, because that's kind of proof that the required parts are there for software-modifyability (writing software by using software) and also executing it, which involves the same constructs that are needed for other programs (as these too deal with the same 1-5).

Or otherwise, if your language satisfies these minimal requirements, any other program (as a description-of/solution-to a problem) that may be written in some other language might as well be written in yours, however crude (like, if you had to synthesize numerical arithmetic from binary comparisons you store and pull back from memory, calculating memory addresses in your virtual or physical stack by the same method, implementing the "next" counter and its jumps to new addresses where there's new instructions by the same method, dispatching your instruction set to implementations by the same method, the implementation being constructed by the same method, etc.).

There's very primitive "environments" which were proven to be Turing complete, for example Conway's Game of Life (not really having convenient 4 logic nor 5 control and instead needs to be made up for with clever patterns) or XSLT (not really having 3 memory, version 1.0 less so, newer versions maybe more so, but passing arguments to parameterizable templates does act as memory of a crude kind), while other types of languages like some query languages (SQL comes to mind, only newer features may push it too towards Turing completeness) or markup languages, lack some of these required criteria. So if your language covers 1-5 in some form, it pretty likely is Turing complete, given less has been proven to be. From there, it mostly becomes a question of usage convenience and execution efficiency, vs. the formal proof of Turing completeness.
---
