Is a Turing machine a real device or an imaginary concept?

Question

When I am studying about Turing machines and PDAs, I was thinking that the first computing device was the Turing machine.

Hence, I thought that there existed a practical machine called the Turing machine and its states could be represented by some special devices (say like flip-flops) and it could accept magnetic tapes as inputs.

Hence I asked how input strings are represented in magnetic tapes, but by the answer and by the details given in my book, I came to know that a Turing machine is somewhat hypothetical.

My question is, how would a Turing machine be implemented practically? For example, how it is used to check spelling errors in our current processors.

Are Turing machines outdated? Or are they still being used?

Biotite

Answer 1

When Turing first devised what are now called Turing machines, he was doing so for purely theoretical reasons (they were used to prove the existence of undecidable problems) and without having actually constructed one in the real world. Fast forward to the present, and with the exception of hobbyists building Turing machines for the fun of doing so, TMs are essentially confined to Theoryland.

Turing machines aren't used in practice for several reasons. For starters, it's impossible to build a true TM, since you'd need infinite resources to construct the infinite tape. (You could imagine building TMs with a limited amount of tape, then adding more tape in as necessary, though.) Moreover, Turing machines are inherently slower than other models of computation because of the sequential nature of their data access. Turing machines cannot, for example, jump into the middle of an array without first walking across all the elements of the array that it wants to skip. On top of that, Turing machines are extremely difficult to design. Try writing a Turing machine to sort a list of 32-bit integers, for example. (Actually, please don't. It's really hard!)

This then begs the question... why study Turing machines at all? Fortunately, there are a huge number of reasons to do this:

1. To reason about the limits of what could possibly be computed. Because Turing machines are capable of simulating any computer on planet earth (or, according to the Church-Turing thesis, any physically realizable computing device), if we can show the limits of what Turing machines can compute, we can demonstrate the limits of what could ever hope to be accomplished on an actual computer.

2. To formalize the definition of an algorithm. Why is binary search an algorithm while the statement "guess the answer" is not? In order to answer this question, we have to have a formal model of what a computer is and what an algorithm means. Having the Turing machine as a model of computation allows us to rigorously define what an algorithm is. No one actually ever wants to translate algorithms into the format, but the ability to do so gives the field of algorithms and computability theory a firm mathematical grounding.

3. To formalize definitions of deterministic and nondeterministic algorithms. Probably the biggest open question in computer science right now is whether P = NP. This question only makes sense if you have a formal definition for P and NP, and these in turn require definitions if deterministic and nndeterministic computation (though technically they could be defined using second-order logic). Having the Turing machine then allows us to talk about important problems in NP, along with giving us a way to find NP-complete problems. For example, the proof that SAT is NP-complete uses the fact that SAT can be used to encode a Turing machine and it's execution on an input.

Hope this helps!

Stigmasterol

What's P and NP? – Stopover

@Stopover They're complexity classes, groups of problems that, intuitively, are defined by how hard they are. Do a quick Google search for "P versus NP" and you'll find some great resources - it's an exciting topic! – Stigmasterol

"Turing machines are capable of simulating any computer on planet earth", I just wonder, is it possible, that simulating a computer would mean that a given computer, which is not simulated, but can be simulated by a TM has better computational complexity, than the simulated counterpart on a TM. I mean, that when searching for ex. time complexity for a problem on a TM, we do not find the actual time complexity of the computer, which is being simulated by the TM and it would be different if it was an "actual" computer? @Stigmasterol – Sonjasonnet

Answer 2

It is a conceptual device that is not realizable (due to the requirement of infinite tape). Some people have built physical realizations of a Turing machine, but it is not a true Turing machine due to physical limitations.

Here's a video of one: http://www.youtube.com/watch?v=E3keLeMwfHY

Calzada

Are turing machines are outdated? or How it is used in current date? – Biotite

They are saying "infinite tape" in theory bcz to generalize for all cases. But I think we know how long theinput or stack of our case will take.(at least approximately) – Biotite

They are a mathematical concept created for the study of algorithmic computation. They cannot be 'outdated' because they are just an idea. An alternate idea for the study of computation came from Alonzo Church with his Lambda Calculus. They are not real machines but abstract notions used for proof and study. – Calzada

How it is used in current date? It will be better for me,when you give a practical example. And turing machine is a study of what? where PDA is used? PDA is implemented in turing machine since they doesnt have primary memory right in that day! – Biotite

Answer 3

It's a theoretical machine, the following paragraph from Wikipedia

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

This machine along with other machines like non-deterministic machine (doesn't exist in real) are very useful in calculating complexity and prove that one algorithm is harder than another or one algorithm is not solvable...etc

Trattoria

Answer 4

Turing Machine are not exactly physical machines, instead they are basically conceptual machine. Turing concept is hypothesis and this is very difficult to implement in real world since we require infinite tapes for small and easy solution too.

Necrose

That answer doesn't really contribute anything that the previous answers missed. – Iey

Answer 5

Turing machine (TM) is a mathematical model for computing devices. It is the smallest model that can really compute. In fact, the computer that you are using is a very big TM. TM is not outdated. We have other models for computation but this one was used to build the current computers and because of that, we owe a lot to Alan Turing who proposed this model in 1936.

She