Printable View
:cry: im having difficulty in understanding turing machines :( if anyone can help can they explain to me the following:-
a turing machine starts off with its read/write head at the leftmost bit of the binary representation of an arbitary numbern, and terminates with its read/write head at the leftmost bit of the binary representation of n + 1.
thanks in advance :wave:
Which part doesn't make sense?
A turing machine is a state automaton that operates on an infinite tape with a finite amount of symbols, in a finite alphabet, according to a finite instruction set, having a finite amount of states. Each instruction is a cartesian product of these elements:
input symbol (which is read from the tape)
output symbol (which is written to the tape)
the state in which the instruction executes
the consequent state.
Right/Left (depending on which direction on the tape the read/write head will move)
a binary representation of a number, is a number written using only two digits, 0 and 1, where digit n is the number/2^(n-1) modulus 2.
I think a Turing machine can only do a few operations (less than 10-20). Try a Web search to find out what operations are allowed. It should be a lot simpler to understand than the posted description of this hypothetical device.
Turing proved that his simple machine could do anything that more complicated machines could do. Since it was easier to analyze than a complex device, it could be used to determine the theoretical capabilities of more complex systems.
Turing machines are cool but they are very hard to program.
10-20, where did you get that number? :DQuote:
Originally Posted by Guv
There should only be one kind of instruction, which looks like this:
(StateA, StateB, Read, Write, Direction)
For instance, if I have a tape looking like this:
[..A,B,C,D..]
the head is on B, and the TM is in state X,
and we have this instruction:
(X,Y,B,E,Right)
then what follows is
[..A,E,C,D..]
the head is now on C, and the TM is in state Y.
Six operations are allowed.
http://www.alanturing.net/turing_arc...20Machine.htmlQuote:
* read (i.e. identify) the symbol currently under the head
* write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
* move the tape left one square
* move the tape right one square
* change state
* halt.
yeah ok, if thats what you mean by operation.. but then again you could have so many more operations...
Kedaman: Sorry if I mislead anybody. It has been a long time since I read anything about Turing machines. I only remembered that they had very few instructions, which made it easy to analyze their capabilities.
Note that I said less than 10-20 instructions, rather than 10-20, and also suggested a Web Search to discover the correct information.
I'm pretty sure that it only goes in one direction of flow, also. I just couldn't find anyhwere to support it.
Guv: Yeah you said it was less than 10-20 quite correct there ;) Maybe i'm the one being misleading..
After checking out the link, seeing each of the so called atomic operations I thought it was misleading, to say that a TM consist of occurrences of these atomic operations, as if they were valid instructions in themselves, which they are not. Each instruction is a set of 4 of the atomic operations, one of which can be movement on the tape to either left or right, and the halt operation occurrs only if the TM comes to a halting state, so basically that operation is a kind of change state operation. Read and write always occurr, although you can write the same letter you've read, to simulate a missing write operation. A missing read operation means copying the same instruction for each possible symbol on the tape. Furthermore the most important operation got unmentioned, that the writing, moving and changing state can be conditioned, to the reading and the current state (which it is by default though, so to make something categorical, you need to condition all possible states and tape symbols). Of course otherwise, in an abstract sense , a string of these atomic operations can be translated to valid TM instructions, but you kind of lose the point if these operations can't be conditioned. Of course that depends on how you define "operation". Sorry for the confusion.
dglienna: what do you mean by one direction of flow?
I thought the instruction set was on a loop, so that directional flow was in one direction. I know you can have moves back and forth and skipping conditionally, but after each cycle, the 'tape' would be at the beginning again.
Well its not the tape that contains the instructions, the tape is for input/output
There's no instruction pointer either, but that and all variables in any imperative programming language make up the states of the TM.
some pseudo code for implementing a (restricted) TM could look like this:
variables:
currentstate=startstate
tapehead
haltstate
state[]
tape[]
instructions[][]
while(currentstate!=haltstate)
{
i=instructions[currentstate][tape[tapehead] ]
currentstate=i.nextstate
tape[tapehead]=i.write
if (i.moveright)tapehead++; else tapehead--;
}
Don't forget that the turing machine has the IF instruction!