0
$\begingroup$

I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I understand they are a sort of a basis for CS topics).

I've also seen comments by some members mentioning turing-completeness (Particularly when dealing with programming languages) and was just looking for some clarification.

I did search around before posting this and haven't been able to find a similar post or a website that describes this in terms that I have been able to understand or decipher. Thanks.

Improve this question
$\endgroup$
3
  • $\begingroup$ This isn't on topic here, since it's not a security question. I've voted to close, but will see if someone can migrate to CompSci. $\endgroup$
    – Polynomial
    Commented Dec 19, 2012 at 16:01
  • $\begingroup$ Probably a question best for cstheory.se. $\endgroup$
    – Rook
    Commented Dec 19, 2012 at 16:05
  • $\begingroup$ Ahh sorry I didn't know there was a CompSci. If it can't move just close and I will post it again on cs.se. Thanks. $\endgroup$
    – JZeolla
    Commented Dec 19, 2012 at 17:27

3 Answers 3

Reset to default
1
$\begingroup$

A Turing machine is named after British mathematician Alan Turing; he first described them in his paper "On computable numbers, with an application to the Entscheidungsproblem". It serves as the mathematical basis of computation and allowed various notions of computability to be mathematically proven even before physical computers existed.

Using Turing machines we can reason about what algorithms are fundamentally unsolvable, which ones are solvable in a reasonable amount of time, and which ones are solvable but take an unreasonable amount of time. Here, "reasonable" means the algorithm goes through a number of steps which is polynomial in the length of the input. For example, being able to prove mathematically that it is very hard to calculate the two prime factors of a large composite number is the underpinning of the security of the internet, the RSA algorithm.

The basic Turing machine consists of a 'tape' divided into 'cells', where each cell contains either a symbol or a blank; and a read/write head which can read symbols from the tape, write symbols onto the tape and move left or right along the tape. The action of the head is given by a transition function, which basically has a bunch of rules like "if you are in state q1 and you read an X, replace the X with a Y, move the head one cell right, and change to state q2".

The Church-Turing thesis is what makes Turing machines useful: simply put, states that a function is algorithmically computable if and only if there is a Turing machine which can compute it.

A language is Turing complete if and only if it can be used to simulate any single-taped Turing machine. Due to the Church-Turing thesis, this means it can be used to compute any algorithmically-solvable function.

As an interesting aside, a machine with only the instruction "subtract and branch if less than or equal" (see one instruction set computer) is actually Turing complete: it has conditional branching and the ability to change arbitrary memory locations, which is all that is required.

I recommend Sipser's "Introduction to the Theory of Computation" for a grounding in this stuff.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great answer, and thank you for that book recommendation. I'm buying it now. $\endgroup$
    – JZeolla
    Commented Dec 20, 2012 at 13:00
3
$\begingroup$

A Turing machine is a simple theoretical/conceptual computational device based on state. Computation is done through state transitions based on the machines current state. It is popular in Computer Science theory due to how models and proofs can be built off of it. Wikipedia has a far more detailed write up on Turing machines than is practical to put here and a general discussion of Turing machines is probably off topic for IT Security. Computer Science is probably a good place to ask more about Turing machines in general, since they are a fundamental conceptual device for Computer Science theory.

In case you are a visual-learner, interestingly enough, there exist physical incarnations of the abstract device.

Improve this answer
$\endgroup$
0
0
$\begingroup$

The "Turing" machine was described in 1936 by Alan Turing[1] who called it an "a-machine" (automatic machine). The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation. from Wikipedia.

This was hard for me to understand as well, since that is something as they described hypothetical device just to let computer scientists understand how the CUP process the instructions.

I think this is a very nice article to read : http://en.wikipedia.org/wiki/Turing_machine

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I wouldn't agree that it is "just to let computer scientists understand how the CPU processes instructions" as it isn't much to do with physical CPUs, really. As I said in my answer, it's more to do with the theoretical underpinning. $\endgroup$
    – sjmeverett
    Commented Dec 20, 2012 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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