DarkLordoftheMonkeys

I'm trying to learn programming as well as I can. I've found that there's still much that I have to learn, and much that I have yet to grasp. A lot of what I need to grasp is theory, because in order to understand computers, well enough to program them effectively, I have to understand computer science. This is why I've done as much research as I can on discrete mathematics, algorithms, data structures, BNF, etc.

Today I came to the topic of Turing completeness, something I had been meaning to explore for some time. I already knew the definition of a Turing-complete language, that is, a language that can simulate the operation of a Turing machine. I already knew the four parts it has to simulate: the head (I/O mechanism), the tape (memory and I/O interface), the instruction table (the program), and the state register (transient memory). Not sure if I got all those right.

The thing that I couldn't figure out was what precisely were the minimal syntactic requirements for a Turing-complete language. I looked it up on Wikipedia, and the article had this to say:

To be Turing complete, it is enough to have conditional branching (an "if" and "goto" statement), and the ability to change memory.

So if I understand correctly, the minimal requirements are something along the lines of:

- At least one data type, with the requirement that it must either be numerical or be able to simulate a numerical type.

- Numerical operations, at the minimum either incrementation and decrementation, or addition and subtraction.

- A conditional statement.

- An unconditional branch.

- Or, as an alternative to the last two, a logical loop.

The if and goto statements can be combined to simulate logical looping, iteration, and recursion. A while loop can simulate an if statement by using a conditional and a counter as its looping condition and executing only once. It can also simulate a goto statement by using a true value as its conditional and thus looping indefinitely.

This leads to the question of whether sed is Turing-complete. I always found sed interesting because of its bizarre syntax and the way it handles control flow and I/O. sed has a single variable, called the hold space, which can be used to simulate either an integer or a string. Addition and subtraction can be done by appending to and deleting/rebuilding the hold space, and its value can be queried by swapping it with the current pattern space and addressing it with a regular expression. I can simulate a while loop with it, like this:

Code:

:start
/TC/bend
n
# do stuff to the addressed lines
bstart
:end

where TC is the pattern that terminates the loop.

This code snippet uses a conditional (the line address) and an unconditional branch (the goto statement b) to build a working while loop.

The problem with sed is it can not do I/O normally. It reads from a file and sends its output to standard output. It has a state register, which can store multiple variables (represented by the occurrences of specified characters), an instruction table, and I/O. The problem is it can't operate without a host file. So one could say it's not Turing-complete because it can't operate on its own, in the same way that people say viruses don't count as life because they can not reproduce without a host cell. I suppose it is possible to solve any problem with sed, but it would be extremely difficult.

Someday, when I learn about compiler design, I want to create my own language that has only the minimal requirements for Turing-completeness. It'll be an esoteric language, obviously, something that programmers can use to test the limits of programming. But that's a long way off.

Right now, I'm sort of daunted by the realization of how little I know or understand, even after studying this stuff for seven months. It's going to be a long road.