Halting Problem

9 Key excerpts on "Halting Problem"

• 

  eBook - ePub

  The Most Complex Machine

  A Survey of Computers and Computing

  • David J. Eck(Author)
  • 2018(Publication Date)
  • A K Peters/CRC Press

    (Publisher)

  But you might find a machine that makes correct predictions in a great many cases, perhaps even for all the cases that you are really interested in. In fact, if you are designing Turing machines, or writing programs, there is nothing to stop you from consciously trying to produce machines or programs whose behavior can be analyzed. The lesson that a programmer should learn from the unsolvability of the Halting Problem is not that it is impossible to write good programs, but rather that good programs don’t happen automatically. I will have more to say in Chapters 6 and 7 about techniques for writing good programs. Furthermore, our proof says nothing, one way or the other, about whether people can solve the Halting Problem. It is still conceivable that, given any Turing machine and input, you might eventually be able to decide whether or not that machine will halt on that input. However, you will not be able to write down a fixed set of rules that can be used to make the decision in all cases, since once you had done so, you could build a Turing machine that solves the Halting Problem by following those rules. (Though how you could ever be sure that you would get the right answer in all cases without writing down a set of rules, I have no idea!) 4.3.2. Other Problems. The Halting Problem is only the first of many unsolvable problems. There are many natural questions that can be asked about computers and Turing machines that cannot be answered—not, at least, by a Turing machine or a computer program. Here is a sampling of such problems. In each case, saying that the problem is unsolvable means that there is no Turing machine that can correctly answer the problem in all cases: • Given any Turing machine T, determine whether T will ever halt after being started on an empty tape. • Given a Turing machine T, determine whether there is any number n such that T will halt when started on input n. • Given a Turing machine T, determine whether it computes a function from N to N

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures and Algorithm Analysis in Java, Third Edition

  • Clifford A. Shaffer(Author)
  • 2012(Publication Date)
  • Dover Publications

    (Publisher)

  Ehalt . Thus, the problem of determining if a program will halt on no input must be unsolvable.

  Example 17.5 For arbitrary program P , does there exist any input for which P halts?

  Proof: This problem is also uncomputable. Assume that we had a function Ahalt that, when given program P as input would determine if there is some input for which P halts. We could modify our compiler (or write a function as part of a program) to take P and some input string w , and modify it so that w is hardcoded inside P , with P reading no input. Call this modified program P′ . Now, P’ always behaves the same way regardless of its input, because it ignores all input. However, because w is now hardwired inside of P′ , the behavior we get is that of P when given w as input. So, P′ will halt on any arbitrary input if and only if P would halt on input w . We now feed P′ to function Ahalt . If Ahalt could determine that P′ halts on some input, then that is the same as determining that P halts on input w . But we know that that is impossible. Therefore, Ahalt cannot exist.

  There are many things that we would like to have a computer do that are unsolvable. Many of these have to do with program behavior. For example, proving that an arbitrary program is “correct,” that is, proving that a program computes a particular function, is a proof regarding program behavior. As such, what can be accomplished is severely limited. Some other unsolvable problems include:

  • Does a program halt on every input?
  • Does a program compute a particular function?
  • Do two programs compute the same function?
  • Does a particular line in a program get executed?

  This does not mean that a computer program cannot be written that works on special cases, possibly even on most programs that we would be interested in checking. For example, some C compilers will check if the control expression for a while loop is a constant expression that evaluates to false . If it is, the compiler will issue a warning that the while loop code will never be executed. However, it is not possible to write a computer program that can check for all

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Philosophy of Mathematics

  • Dov M. Gabbay, Paul Thagard, John Woods(Authors)
  • 2009(Publication Date)
  • North Holland

    (Publisher)

  The most famous question is this: Does there exist an effective procedure implemented on a Turing machine that decides for any Turing machine M and any input x, whether the computation of machine M for input x terminates or halts? This is the Halting Problem as formulated by Turing in 1936; it is clearly a fundamental issue concerning computations and is unsolvable. The argument is classical and begins by assuming that there is an H that solves the Halting Problem, i.e., for any M and x, ψ H (gn (M), x) = 1 iff M halts for argument x ; otherwise ψ H (z, x) = 0. It is easy to construct a machine H * from H, such that H * halts for x iff ψ H {x, x) = 0. Let h * be gn (H *); then we have the following equivalences: H * halts for h * iff ψ H (h *, h *) = 0 iff ψ H (gn (H *), h *) = 0 iff H * does not halt for h *, a contradiction. Turing used the unsolvability of this problem to establish the unsolvability of related machine problems, the self-halting and the printing problem. For that purpose he implicitly used a notion of effective reducibility; a problem P, identified with a set of natural numbers, is reducible to another problem Q just in case there is a recursive function f, such that for all x : P (x) if and only if Q (f (x)). Thus, if we want to see whether x is in P we compute f (x) and test its membership in Q. In order to obtain his negative answer to the decision problem Turing reduced in a most elegant way the Halting Problem to the decision problem. Thus, if the latter problem were solvable, the former problem would be. The self-Halting Problem K is the simplest in an infinite sequence of increasingly complex and clearly undecidable problems, the so-called jumps. Notice that for a machine M with code e the set K can be defined arithmetically with Kleene’s T-predicate by (∃ y) T (e, e, y). K is indeed complete for sets A that are definable by formulas obtained from recursive ones by prefixing one existential quantifier; i.e., any such A is reducible to K

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Alan Turing

  • S. Barry Cooper, J. van Leeuwen(Authors)
  • 2013(Publication Date)
  • Elsevier Science

    (Publisher)

  The Word Problem in Semi-Groups with Cancellation

  (Annals of Mathematics, vol. 52, no. 2 (1950), pp. 491–505)

  Gregory Chaitin on — Finding the Halting Problem and the Halting Probability in Traditional Mathematics

  Following Turing’s 1936 discovery of the Halting Problem and how to derive incompleteness from it as a corollary in On Computable Numbers, a great deal of work was done by many mathematicians finding ‘natural’ versions of the Halting Problem in many traditional areas of mathematics, that is, in pre-Turing mathematics. Turing describes some of this work in his lovely 1954 expository paper Solvable and Unsolvable Problems, movingly published the year of his untimely death. Turing’s word problem paper is a complicated piece of such work that was carried out by Turing himself; obviously he wished to reassure himself that the Halting Problem was ubiquitous in real mathematics, which is the current consensus.1

  This very large body of work, which unfortunately has never been collected in a single book and remains scattered in crumbling, dusty journals, can also be used to show that the halting probability Ω is hiding in many fields of traditional mathematics. For example, using 1947 work of Emil Post, it is easy to show2 that there is a semi-group without cancellation such that for each positive integer k the number of words λq initial a k b n λ which are equal to the word λq final λ is finite or infinite depending on whether the k th bit of Ω is a 0 or a 1. Following work of Toby Ord and Tien D. Kieu (2004), one can replace ‘finite’ or ‘infinite’ here by ‘even’ or ‘odd’.

  Most unfortunately, Turing did not live long enough to see the most beautiful example of the Halting Problem that occurs in a traditional field of mathematics, number theory: namely the 1970 Davis–Putnam–Robinson–Matiyasevich proof, that asking for a general method to determine whether or not a diophantine equation has a solution is equivalent to solving the Halting Problem. In particular, for any computer programming language, there is a diophantine equation with a parameter k that has a solution if and only if the k th computer program in that language ever halts. Similarly, there is a diophantine equation with a parameter k that has finitely or infinitely many solutions — or alternatively an even or an odd number of solutions — depending on whether the k

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  From Algorithms to Thinking Machines

  The New Digital Power

  • Domenico Talia(Author)
  • 2023(Publication Date)
  • ACM Books

    (Publisher)

  A positive solution to a decision problem consists of providing an algorithm for solving it, whereas a negative solution consists of proving that no algorithm for solving that problem exists (i.e., the problem is unsolvable) [ Martin 1958 ]. In 1931, Kurt Gödel published the incompleteness theorems that showed that for any formal system of axioms equipped with rules of inference satisfying certain minimal requirements, there exist questions that cannot be answered within that system (i.e., they are not solvable). Gödel’s incompleteness theorems are the most important proven mathematical statements on the limitations of formal systems. A few years later, Alan Turing reformulated Gödel’s results on the limits of proof and computation, proving that his “universal computing machine” would be capable of performing any possible mathematical computation if it were representable as an algorithm. Turing deduced that if a computation problem cannot be expressed as an algorithm, that is, cannot be executed by a Turing machine, there is no solution for that problem. In particular, Alan Turing and Alonzo Church independently proved that a general solution to the “decision problem” is not possible. Initially, Turing proved the undecidability of the Halting Problem (i.e., the problem of determining, given a description of an arbitrary computer program and an input, whether the program will finish running or will run forever), then, as a corollary, he found the unsolvability of the “decision problem.” In their studies, it is assumed that the intuitive notion of “effectively calculable,” that is, computable through a mechanical method, is captured by the functions computable by a Turing machine or, equivalently, by those expressible in a formalism known as lambda calculus. As mentioned before, Turing proved the theorem that there is no algorithm to solve the Halting Problem. That problem is important because it was also one of the first problems to be proved as being undecidable

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Cybernetical Intelligence

  Engineering Cybernetics with Machine Intelligence

  • Kelvin K. L. Wong(Author)
  • 2023(Publication Date)
  • Wiley-IEEE Press

    (Publisher)

  Table 12.1 .

  Table 12.1

  Table summarizing the parameters of a Turing machine.

  Parameter	Description
  States	A Turing machine has a finite set of states that it can be in. When the machine is in a particular state, it performs a particular action (e.g. read a symbol, write a symbol, and move the tape head).
  Tape	The tape of a Turing machine is divided into discrete cells, each of which can contain a symbol from a finite set of symbols. The tape is initially blank except for a finite sequence of symbols that represent the input.
  Tape head	The tape head of a Turing machine is a read/write head that can move left or right along the tape one cell at a time.
  Alphabet	The alphabet of a Turing machine is the set of symbols that can be written to or read from the tape.
  Transition function	The transition function specifies the behavior of the Turing machine. Given the current state and symbol read from the tape, it specifies the next state of the machine, the symbol to write to the tape, and the direction for the tape head to move (left or right).
  Halting state	The halting state is a special state that indicates that the Turing machine has finished its computation. Once the machine enters the halting state, it stops and outputs the contents of the tape.

  12.1 Behavior of a Turing Machine

  A Turing machine is a theoretical computing machine that operates on an infinite tape of symbols. The behavior of a Turing machine is described by its transition function, which specifies how the machine moves and changes the symbol on the tape based on its current state and the symbol that it is currently reading.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Complexity

  A Philosophical Overview

  • Nicholas Rescher(Author)
  • 2020(Publication Date)
  • Routledge

    (Publisher)

  For with respect to purely theoretical problems it is clear from Turingesque results in algorithmic decision theory (ADT) that there will indeed be computer insolubilia—mathematical questions to which an algorithmic respondent will give the wrong answer or be unable to give any answer at all, no matter how much time is allowed. 4 But this is a mathematical fact which obtains of necessity so that this whole issue can be also set aside for present purposes. For in our present context of generalized problem solving (GPS) the necessitarian facts of Gödel-Church-Turing incompleteness become irrelevant. Here any search for meaningful problem-solving limitations will have to confine its attention to problems that are in principle solvable: demonstrably unsolvable problems are beside the point of present concern because an inability to do what is in principle impossible hardly qualifies as a limitation. The sort of limit that a rigid demonstration of impossibility establishes in our present context is one that bears not so much on question answering as on question askability, seeing that it makes no sense to ask for the demonstrably impossible. For present purposes, then, it is limits of capability not limits of feasibility that matter. In asking about the problem-solving limits of computers we are looking to problems that computers cannot resolve but that other problem solvers conceivably can. The limits that will concern us here are accordingly not rooted in conceptual or logico-mathematical infeasibilities of general principle but rather in performatory limitations imposed upon computers by the world’s modus operandi

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Popular Lectures on Mathematical Logic

  • Hao Wang(Author)
  • 2014(Publication Date)
  • Dover Publications

    (Publisher)

  е). From this it follows that:

       3.6.1. Neither {(x, у) | φx (y)) < ∞} nor {x | φx (x) < ∞} is a recursive set.

  This is usually called the unsolvability of the Halting Problem. But it may be more instructive to think in terms of computer programs especially for those who are more interested in computers.

       3.6.2 The universal Halting Problem. There is no P-program H such that for every P-program P and every finite input tape word W, with descriptions p and w, H(p, w) will always halt and yields an answer 0 or 1 according as P halts on W or not.

  When a program, with input tape, is started in operation, it may take a long time before the1 computation is completed and the machine comes to a halt. The computation may go on forever, i.e., for certain program-tape pairs, it will never halt. And it is natural to ask whether we have a decision procedure to tell us the ‘yes’ or ‘no’ answer in each case. It will not do to take the universal program as giving the procedure since, although if P halts on W, we shall eventually know, we shall never find out merely by operating U persistently that P will never halt on W.

  In fact, 3.6.2 says there can be no such program .at all. Suppose there were such a program H, it would, in particular, also decide for the special case w = p:

  Let H1 be a simple copying program so that

  Combining H1 and H, we get a program H2 :

  In particular, H2 can be so chosen as to halt while scanning the (first) *. Suppose H2 has q lines. Let H3 be obtained from H2 by adding the following:

  Hence, we have:

  Since this is true for every program P, it is true when we take H3 as P. But then we arrive at a contradiction.

  It may be of interest to prove this theorem in terms of actual computers rather than abstract machines. The following proof was communicated to me by Yang Chen-Ning. Since he does not specialize in logic, his proof is likely to be more transparent to a wider group of people.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Philosophy of Computer Science

  An Introduction to the Issues and the Literature

  • William J. Rapaport(Author)
  • 2023(Publication Date)
  • Wiley-Blackwell

    (Publisher)

  2017 .

  For more on “circularity,” see Petzold, 2008 , Ch. 10 , who notes, by the way, that the concept of “halting” was introduced into the modern literature by Martin Davis (Petzold, 2008 , p. 179), “despite the fact that Turing's original machines never halt!” (Petzold, 2008 , p. 329). Here is a slightly different observation:

  The halting theorem is often attributed to Turing in his 1936 paper. In fact, Turing did not discuss the Halting Problem, which was introduced by Martin Davis in about 1952. (Copeland and Proudfoot, 2010 , p. 248, col. 2)

  This is clarified in Bernhardt, 2016 :

  The Halting Problem is probably the most well‐known undecidable decision problem. However, this is not the problem that Turing described in his paper.

  As Turing described his machines, they did not have accept states [i.e. they did not halt]. They were designed to compute real numbers and so would never stop if computing an irrational number. The notion of a Turing machine was changed [from Turing's original ‐machines] to include accept states by Stephen Kleene and Martin Davis. Once you had this new formulation of a Turing machine, you could consider the Halting Problem. Davis [1958] gave the Halting Problem its name. (Bernhardt, 2016 , pp. 120–121; see also p. 142)

  For an analysis of these notions in modern terms, see van Leeuwen and Wiedermann, 2013 .

  8.9.7 “Computable Sequences and Numbers”

  Here are Turing's final definitions from this section. First:

  A sequence

  Sign up to read

  Learn more about book