| dbp:event
|
- Kleene includes a discussion of the unsolvability of the halting problem for Turing machines and reformulates it in terms of machines that "eventually stop", i.e. halt: "...there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops." (en)
- In a paper, Stephen Kleene states that "In setting up a complete algorithmic theory, what we do is describe a procedure ... which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, 'Yes' or 'No,' to the question, 'Is the predicate value true?'." (en)
- Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I". (en)
- Kurt Gödel announces a proof as an answer to the first two of Hilbert's 1928 questions. "At first he [Hilbert] was only angry and frustrated, but then he began to try to deal constructively with the problem... Gödel himself felt—and expressed the thought in his paper—that his work did not contradict Hilbert's formalistic point of view". (en)
- Hilbert recasts his 'Second Problem' at the Bologna International Congress. He posed three questions: i.e. #1: Was mathematics complete? #2: Was mathematics consistent? #3: Was mathematics decidable? The third question is known as the Entscheidungsproblem . (en)
- Emil Post explores the halting problem for tag systems, regarding it as a candidate for unsolvability. Its unsolvability was not established until much later, by Marvin Minsky. (en)
- Martin Davis uses the term 'halting problem' in a series of lectures at the Control Systems Laboratory at the University of Illinois in 1952. It is likely that this is the first such use of the term. (en)
- David Hilbert poses his "23 questions" at the Second International Congress of Mathematicians in Paris. "Of these, the second was that of proving the consistency of the 'Peano axioms' on which, as he had shown, the rigour of mathematics depended". (en)
- Alonzo Church publishes "An Unsolvable Problem of Elementary Number Theory", which proposes that the intuitive notion of an effectively calculable function can be formalized by the general recursive functions or equivalently by the lambda-definable functions. He proves that the halting problem for lambda calculus is not effectively calculable. (en)
- Church publishes the first proof that the Entscheidungsproblem is unsolvable, using a notion of calculation by recursive functions. (en)
- J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing. (en)
- Alan Turing's paper On Computable Numbers With an Application to the Entscheidungsproblem goes to press in May 1936 and reaches print in January 1937. Turing proves three problems undecidable: the "satisfaction" problem, the "printing" problem, and the Entscheidungsproblem. Turing's proof differs from Church's by introducing the notion of computation by machine. This is one of the "first examples of decision problems proved unsolvable". (en)
- Emil Post's paper "Finite Combinatory Processes. Formulation I" is received. Post adds to his "process" an instruction " Stop". He called such a process "type 1 ... if the process it determines terminates for each specific problem." (en)
|
