# Is this language Turing-Complete?

I recently made an esoteric programming language, and I want to know how to test and see if the language is Turing-Complete. Most places I looked said it needed infinite loops and infinite data storage. Is that all?

Also, do I need to simulate a Turing Machine for proof, or is there an easier way?

It is called NOR and it's pretty different from most EPL's that I've seen: NOR

• You don't have any way to make a decision. Your language is most definitely not Turing-complete. Oct 8, 2016 at 21:01
• @SebastianRedl It does in a way have conditionals. Of you do "10 NOR IN0, 0" it would essentially be he same as saying "if(IN0 = 0) line10 = 1 else line10 = 0 Oct 8, 2016 at 21:39
• How does your language have infinite storage? It seems to be limited to one value per line? Oct 8, 2016 at 21:43
• @WinstonEwert yes, but the amount of lines you can have is infinite. (Not practically, but language-wise you can). So the "tape" could be an infinite string of 0's and 1's, and the index of the tape (ie where the head is when reading or writing that value) corresponds to the line numbers. Oct 8, 2016 at 21:46

No.

I can prove that language isn't turing complete, because I can solve the halting problem for it. In fact, I can do so in two different ways, each exploiting a different aspects of your language.

Firstly, none of your branches are conditional. None of the calculated values affects whether or not a jump is taken. This means that once you've entered a loop, you are always in an infinite loop. Any time the same line of code is executed twice, I know the program is in an infinite loop. Thus I can tell whether or not a program will halt by observing its execution. It will either finish (in which case it halts) or start repeating lines of execution (in which case it will never halt).

Secondly, your memory size is fixed. Yes, you can have longer programs and thus get more memory, but once a program starts, the amount of memory is fixed. This means that for a program with `n` lines, I know that there are only `2^n*n` possible states for the program. This means that if a program does not halt within the first `2^n*n` steps, it must be in a previously visited state and thus in an infinite loop. Consequently, I can test for halting by simply observing the program to see if it halts within `2^n*n` steps.

There are lots of ways of being turing complete, but for a language similiar to yours, you need actually unbounded memory and conditional branches.

• This is a much better answer than mine. Somehow, I got so bogged down into the detail sub-questions the OP asked that I forgot to look at the "big" question. Oct 8, 2016 at 23:14

I recently made an esoteric programming language, and I want to know how to test and see if the language is Turing-Complete.

Your language is "Turing-complete" if it can simulate any arbitrary single-state Turing machine. Alternatively, by the definition of Turing-completeness, your language is also Turing-complete if it can simulate any other Turing-complete language or computational model, like λ-calculus, µ-recursive functions, the `WHILE` language, the SK(I) combinator calculus, a cyclic tag system, Brainfuck, Rule 110, Conway's Game of Life, , , , + , :2003, …

Most places I looked said it needed infinite loops and infinite data storage. Is that all?

There are many, many ways in which a language can be Turing-complete. Conditional branching plus the ability to manipulate unbounded memory are one example. (This is the minimal feature set for non-pathological, non-esoteric "normal" imperative languages.)

But, say, λ-calculus doesn't have loops, and doesn't have data storage; it doesn't even have "data" at all. It only has two things: function abstraction and function application. Still, that is enough for it being Turing-complete.

Also, do I need to simulate a Turing Machine for proof, or is there an easier way?

You need to simulate, or need to prove that you can simulate, some Turing-complete language or system. It doesn't have to be related to Turing Machines at all, it only has to be Turing-complete.

Note: it is not enough to simulate a Turing Machine. You either need to simulate any single-tape Turing Machine, or a Universal Turing Machine (which itself can simulate any single-tape Turing Machine).

• This is a good reference for when I me my next language and try to make it Turing complete! Oct 8, 2016 at 22:47
• I expanded the answer with references. Oct 8, 2016 at 23:11