Рефераты / Иностранные языки /

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

actually solving problems with the machine but rather in investigating what kinds of problems it could solve and what kinds it could not. Turing discovered that even a machine as simple as this one could solve any problem for which an algorithm could be devised. The computation might be laborious and indirect, but given enough time and paper tape the machine would eventually find the solution and halt. Reduced to its essentials the Turing machine is a language for stating algorithms, as powerful in principle as the more sophisticated languages now employed for communicating with computers. In addition to conceiving, these machines Turing demonstrated, their limitations. In 1936 he showed that there are problems that cannot be solved by Turing machines, and it follows that these problems cannot be solved by any automatic computer. They are problems for which algorithms cannot be written, even in principle. The example first studied by Turing is the problem of predicting whether a particular Turing machine, once it is set in motion, will ever finish its calculation and halt. Through an analysis of this problem he was able to show that there can be no general procedure for telling whether mathematical propositions are true or false. Since then a variety of other problems with the same properties have been proposed. One result of Turing's work was to divide all imaginable problems in mathematics into two classes. Those problems for which algorithms can never be written are in a formal sense permanently unsolvable. Some instances of these problems may be solved by rare perception or by luck, but a general method for their solution will never be found. All other problems in mathematics and logic can be solved by algorithms. As we have seen, however, some algorithms are more useful than others. The class of solvable problems can therefore be divided into two subgroups: those for which there are efficient, polynomial-time algorithms and those for which there are only exponential-time algorithms. Euler's problem is a member of the class with polynomial-time solutions, since Euler's method is itself a polynomial-time algorithm. Problems that can be proved to have only exponential-time algorithms are also known, although they are rather obscure. Although these two groups of problems are quite distinct, it is not always a straightforward task to assign a problem to one group or the other. Indeed, a very interesting class of problems seems to fall somewhere between them. For these problems no efficient algorithms are known and the best available solutions require exponentially increasing time, yet no one has been able to prove that the problems do not have polynomial-time solutions. One such problem was considered in the 19th century by the Irish mathematician William Rowan Hamilton. Superficially Hamilton's problem is much like Euler's .The problem is to decide whether a given graph has a path that takes in each point exactly once (whereas Euler looked for a path that traversed each line once). Actually the tasks are quite different, and Euler's method cannot be applied to Hamilton's problem. The graph derived from the plan of the park at Koenigsberg has a Hamiltonian path, although, as we have seen, it has no Eulerian path. On the other hand, removing two lines results in a graph that has an Eulerian path but not a Hamiltonian one. Many other graphs have neither kind of path.

Hamilton's problem can be solved by exhaustive
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ