Thread: C++ Turing machine

Im trying to simulate a turing machine in C++... The problem isnt related to the language... The problem is about the virtual turing machine itself, and that is why Im posting here since I dont know where to post.

The VTM can go right, left, write to the current cell(which is represented by a single byte on the memory), read the current cell and compare the current cell to some value, execute some action if it is evaluated to true or false, saving states and change states. It is everything acomplished by a "pseudo language" I created for the program, which will interpret it "on the fly"

But the problem is that Im not too sure about how a turing machine works, meaning that I don't know what to add to the program and the pseudo language anymore... For example those "machine states", they work more like labels... When you save a state, you're actually saving a position on the pseudo code you can call from any other point, much like a "goto", except for the fact that it is interpreted on the fly. Then we have the pseudo language compare instrutions... I dont even know if a turing machine can compare values... The real problem here is that I dont know turing machines very well... I have no idea how states work, if it is like goto instructions or something else... Finally, the "tape" is represented by contiguous memory locations...

Lets go to the main question... Is it finished? Can it be considered a turing machine? Or is it away from being a turing machine? If Im right so far, what should I do to finish it?

Again it has nothing to do with C++, I know how to use it to do what I want, I just wanna know now what to do next...

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

That is what I was trying to acomplish, so by this definition it is finished. I asked because Im not sure if that is all, since it is easy to do.

When you do something for the first time and find it easy, you start to think you missed something. If all I have to do is to create a mechanism capable of simulating goto and ifs statements, then it is done and all that is left to do is to optimize it.

First off, you shouldn't be concerned that it is too simple - there are *extremely* simple models of computation out there which result in turing machines, i.e. a universal computer. For example, it is possible using only a single machine instruction to be turing complete - the One instruction set computer - Wikipedia, the free encyclopedia . There is also the SKI calculus, in which computation can be reduced to the S and K combinators (and I is simply for convenience.) Do not be deceived by simplicity here, because turing machines can be very small - they are a model for representing computation.

A turing machine's *state* is simply a state in which a program can be in - for example, a door is in the state of 'open' or 'closed', and depending on that state, you may go through the door, or walk away, which are two distinct 'output' states which you transition to, given the initial state. A turing machine somewhat describes the rules for these state transitions.

As an example from Turing himself, here is a very simple example - a machine which outputs the sequence '0 <blank> 1 <blank> 0 <blank> 1 <blank>' on tape memory. That's all it's doing, is computing this string.

We can model this formally. Let's say we have a set of states:

S = (a, b, c, d)

Now, we have our infinite tape, and a set of states the machine can be in. In order to go from one state to the next, we describe a transition function, let's call it t. We can describe this transition function as having a domain and codomain as follows:

t : (S, T) -> (O, S)

What does this mean? Well, here we will say that S is the set of states (we defined above,) T is the current tape symbol, and O is an operation to perform on the given current tape symbol (including movement.)

So basically what this means is that t is the transition function taking as input a pair: an input state and the current tape symbol, and outputs an operation to perform on the tape, followed by a final state to transition to. So you can think of t as the function which makes the computer 'go'.

But how do we define t to do what we wanted, namely output the string "0 1 0 1 0 1 0 1"? We do it like this, where I'll say e denotes the 'blank tape symbol', the P function writes a value at the current tape head, and R moves the tape head one over to the right. Basically we are defining a system of equations:

t (a, e) = ( P0 R, b)
t (b, e) = ( R, c )
t (c, e) = ( P1 R, d)
t (d, e) = ( R, a )

So, given initial state 'a' with empty tape, we will write the value '0' to the tape and move one to the right, skip the one, and then write 1, skip the next one, and loop. This is how we describe a turing machine - or a computation. You can think of the state set S as being the set of 'instructions' and the t function moves from one instruction to the next depending on the current machine tape. This example can actually be reduced to a single state 'a' and defining the transition function slightly differently - you can see it here on wikipedia: Turing machine examples - Wikipedia, the free encyclopedia

But what's important to note here is that this is just an abstract model for representing comptuation. You could say describe a machine which computes PNG output and writes every individual byte of the PNG file to locations in tape memory, and thus the overall 'tape memory' could be seen as a PNG file if you wanted to, i.e. the resulting memory from the computer's computation is a PNG file. Also keep in mind the reason turing machines have infinite tape memory is so that you can model any computable procedure without regards to how much memory is needed.

This is just a means of describing a formal computation - that's the important thing. The nice property is that we can describe turing machines very nicely and formally using mathematics; the actual mathematical, formal definition of a turing machine is a bit more complete than what I've described (short story: it can be seen as a 7-tuple representing tape alphabet, states, input states, the transition function and all possible output states and a few other things.)

Does that help any?

As to whether or not your program is 'done' - sure, it can compute anything computable by any other turing machine. Just like any programming language. The rest is all abstraction, right? That's true, but it's deceivingly false as well, because the abstractions mean a lot. You may want to read about what we like to call the 'Turing tarpit' here, "in which everything is possible but nothing of interest is easy."

Awesome explanation, and nice links thanks. Sorry it took some time for me to answer, I havent visited the forum in a while.

That was all I wanted to know about states... I tried to simulate that, but by then I didnt know exactly how states worked, then I ended up creating something a "little" different from what I intented, where you move to another point in the pseudo code and executes the instructions there. In the end it mimics a programming language and is able to do many computations, including things I believe arent necessary, but isnt exatcly what I wanted...

I finished the program, but maybe I'll create another one after spending some more time reading about turing machines... For some reason I find this a really nice subject

Thank you