I am having trouble in writing the specific role of Turing machine? can it solve all the algorithm a digital computer can solve(i.e. today's PC's)?
2
-
$\begingroup$ What do you mean by "role"? $\endgroup$– RaphaelCommented Dec 21, 2017 at 18:41
-
1$\begingroup$ A turing machine is a model of computation. Your question is unclear. $\endgroup$– mikeazoCommented Dec 21, 2017 at 20:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The Turing machine is a theoretical computational model which is studied in undergraduate courses due to its simplicity and for historical reasons.
Historically, the Turing machine was the first widely accepted definition of computation, and for many years, it was arguably the simplest definition to explain. Nowadays, however, we can define computation equivalently using our favorite programming language – one of the wonders of computability theory is that there are many models of computation which are completely equivalent in power, as long as we don't care too much about time and space usage. Turing machines are also polynomially equivalent to RAM machines, and so to imperative languages, and this means that you can define the classes P and NP using either Turing machines or (say) C programs, and obtain completely equivalent definitions.
Turing machines have the advantage that their semantics are very simple to state and analyze. While it is still a big mess to construct a universal Turing machine (in this sense Turing machines are not better than C programs), other basic theorems lend themselves to an easy proof using the Turing machine model. The most obvious example is the Cook–Levin theorem, which states that SAT is NP-complete. Complexity classes with limited resources also have relatively simple definitions using Turing machines (for example, logspace), whereas a definition using C programs would have to be somewhat subtler.
Modern computers are based not on the Turing machine but instead on ideas of von Neumann. In this sense the Turing machine is not a realistic model, and generally speaking the RAM model should be prefered. However, the RAM model has several different variants which are not equivalent, whereas Turing machines are more standardized, with different variants being mostly essentially equivalent (even when time and space usage are measured).
answered Dec 22, 2017 at 12:56
$\begingroup$
$\endgroup$
1
Well there's no existing algorithm on a computer that can execute a program with the ability of a Turing machine yet, as a Turing machine can solve problems like NP-complete exactly, whereas existing algorithms are mostly approximations and not a perfect algorithm.
-
1$\begingroup$ Name any NP-complete problem that I cannot write an algorithm for that will run on existing computers. There aren't any. They may not terminate before I die or the sun explodes, but I can surely write the algorithm. $\endgroup$– mikeazoCommented Dec 21, 2017 at 20:00