Is this language Turing-Complete?

Question

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

Answer 1

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.

Answer 2

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, java, scheme, php, html5 + css3, sql: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.

For example, SQL was shown to be Turing-complete by implementing a cyclic tag system, HTML5+CSS3 was shown to be Turing-complete by implementing Rule 110, Scala's type system was shown to be Turing-complete by implementing the SKI combinator calculus.

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).