1

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. – Sebastian Redl Oct 8 '16 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 – Blue Okiris Oct 8 '16 at 21:39
  • How does your language have infinite storage? It seems to be limited to one value per line? – Winston Ewert Oct 8 '16 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. – Blue Okiris Oct 8 '16 at 21:46
10

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.

  • 2
    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. – Jörg W Mittag Oct 8 '16 at 23:14
6

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.

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

  • This is a good reference for when I me my next language and try to make it Turing complete! – Blue Okiris Oct 8 '16 at 22:47
  • I expanded the answer with references. – Jörg W Mittag Oct 8 '16 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.