text:
Talk:Decision problem

Untitled
Since the definition of "decision problem" refers to the idea of "problem", I think we should have a page defining what that is.

Complete rewrite
I did a complete rewrite of the article. The main problems I tried to fix were
 * 1) article to verbose without using any well defined concepts
 * 2) mixed word problem (computability) with general concept of decision problem, which I think should be separate

MathMartin 13:46, 19 Nov 2004 (UTC)

 * I like the brevity, but it seems to focus strongly on computability theory, particularly in the examples section. I'll add some example problems important in complexity theory and make a note that the list is only a few important examples. Deco 18:55, 19 Nov 2004 (UTC)

I've edited again because there is a difference between computability and decidability. I've also created a similar looking computation problem stub. The class of decidable problems is reducible to the class of computable functions.

We should add interesting classes of questions that are decidable. I.e., subsets of the predicate calculus that are decidable (i.e. monadic predicate logic, all valid formulas, etc.), the propositional calculus, trivially any finite set (not so interesting I suppose), and so on. Nortexoid 02:02, 23 Nov 2004 (UTC)

Examples, Simpler Please
I thought Wikipedia is an encyclopedia, not an entry-portal to an article in the AMS. I's a pretty tough read for a non-specialist. A budding mathematician (e.g. interested undergrad or high-school math whiz or engineer/scientist not in the field) would be stumped. One place to start would be some relatively examples or a progression from an "easier read" into the deep stuff (or visa versa, but both). Ideas? wvbaileyWvbailey 17:14, 10 January 2006 (UTC)

Notes section
I am moving this from the main page for now.

 * It should be noted that a decision problem is always a set of related problems which is in some sense large enough. A single problem P is always trivially decidable by assigning the constant function f(P)≡0 or f(P)≡1 to it.

 * Nearly every problem can be cast as a decision problem by using reductions, often with little effect on the amount of time or space needed to solve the problem. Many traditional hard problems have been cast as decision problems because this makes them easier to study and to solve, and proving that these problems are hard suffices to show that more complex problems are hard as well.

The first paragraph makes no sense to me. The second seems to have a definition of problem different than decision problem, although the article gives no such definition.

I added a section explaining the equivalence of decision problems and function problems, which I think does an adequate job of replacing the above paragraphs. CMummert 00:11, 27 August 2006 (UTC)

Equivalence with function problem
I think that this section should be rewritten and grown a bit.
 * Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. If this decision problem were effectively solvable then the function problem would be as well.

I am not sure what is the decision problem of the graph... Is it dec: f(x)=y?. Because that's not enough to solve f(x)? efficiently - set of values of f could be very large. If we had this decision problem then it could work: dec: f(x)<y? where < is lexicographical order. For polynomial-time classes length of f(x) is polynomial, and we can use binary search.

Solution to other decision problems can also easily allow to solve function problem (as with f:Hamiltonian path - dec:Hamiltonian graph, by removing edges; f:the shortest Salesman's route - dec:Salesman's route shorter than<k etc.) Maybe we could give some examples.

Effectively - I understand it is all in the perspective of polynomial-time classes and it means "within polynomial time"? With regard to wider not-necessairly-time classes, i suppose it's also true but effectively has different meaning then.

I am still not sure how to rewrite it. Any suggestions? --SalvNaut 23:43, 9 September 2006 (UTC)
 * I couldn't stand it and made some changes :) --SalvNaut 00:01, 10 September 2006 (UTC)

 * This article is not about polynomial time reductions. Here effectively means computably (not necessarily poly time).  The graph of a function f is the set of pairs (x,y) such that f(x)=y.  A search is required to solve a function problem assuming the graph is computable, but this is no big deal.   I reverted to the old version because the new one was much less clear (what is True ?), and wasn't grammatically correct in several places.  I added a caveat, though, that the reduction of function problems to decision problems does not respect poly time. CMummert 00:38, 10 September 2006 (UTC)
 * Thanks, that is much better - example is very good.
 * One more question regarding Definitions: Is it really so that provable is used in the same meaning as semidecidable? I understand it would encompass provability in FOL. For me, provable means something stronger (not necessairly FOL-provable). --SalvNaut 18:05, 10 September 2006 (UTC)
 * I have never seen the word provable used as a synonym for r.e. but I left it there in deference to whoever put it in. Probably some textbook or the other includes it.  The usage makes sense because the set of provable statements of an effectively axiomatized first order theory is r.e. CMummert 22:40, 10 September 2006 (UTC)

Definition Conflict
The article on Recursive set states that any language which is not decidable/computable is undecidable. Here, a language that is not decidable may be either semidecidable or undecidable. Are these separate categories or the same? That is, is a recursively enumerable set considered to be a kind of uncomputable set? 67.180.32.231 08:08, 1 April 2007 (UTC)

 * Yes, a recursively enumerable set that is not recursive is both semidecidable and undecidable. CMummert · talk 12:24, 1 April 2007 (UTC)

Reference
Would someone be so kind as to refer me to the source for this result mentioned in the article? "However, this reduction is more liberal than the standard reduction used in computational complexity..." and so on, about the complexity of characteristic functions differing from standard complexity. I don't see it in Sipser, and I'd like to learn more. 128.32.192.124 01:04, 20 April 2007 (UTC)

 * The user who made that edit gave the following reference and said to look at the appendix. I think that the article is just trying to point out that computational complexity tends to use many-one reductions rather than Turing reductions, but it could be worded more clearly. CMummert · talk 01:14, 20 April 2007 (UTC)

 * Thank you so much! I agree that it should probably simply be rewritten to state what you're saying, although for now I will add the reference. 67.180.4.242 22:15, 21 April 2007 (UTC)

Undecidable problem example?
Is it possible to give a simple example of a decision problem that is not decidable? I checked the referenced article that lists undecidable problems, but they all require too much brainpower to grasp to be useful as an example of the concept. I'm wondering if maybe there are trivial undecidable problems that aren't interesting, but at least demonstrate the concept. Bryan Henderson 15:45, 21 June 2007 (UTC)
 * A popular one for just this purpose are tiling problems, such as those described by Wang tiles. Reference here. Dcoetzee 01:23, 22 June 2007 (UTC)

Merge from Undecidable problem
It has been proposed to merge Undecidable problem into here, but I do not see the point. Decision problems can also be classed into tractable/untractable etc. (rather than decidable/undecidable). Recursive language would be a better target for merge. Tizio 12:41, 8 February 2008 (UTC)
 * Doesn't really matter to me. This is just where I saw stuff on undecidable problems, so I chose here.  --UsaSatsui (talk) 18:06, 8 February 2008 (UTC)
 * I would say no to a merge; as a non-expert I'm finding the subject confusing enough as it is, without jumbling it up even more. (I've recorded there that I'd be against deletion also) Moonraker12 (talk) 13:30, 12 February 2008 (UTC)
 * They are literally and exactly the same topic. The issue here is simply that no redirect existed and a new author created the undecidable problem article instead of expanding and clarifying this one. There is also List of undecidable problems. — Carl (CBM · talk) 14:45, 12 February 2008 (UTC)
 * They are not the same topic. At least, not literally and not exactly. Decision problems can also be divided into tractable/untractable; the relation between decisions problems and function problems is not specific to decidability. I agree that a better division of material could be operated. Tizio 16:32, 12 February 2008 (UTC)
 * I appreciate your concern about computational complexity. Perhaps I should have said that an undecidable problem is a kind of decision problem rather than the same as a decision problem. The recursive language article is another issue entirely. — Carl (CBM · talk) 16:42, 12 February 2008 (UTC)
 * Yes, that's precisely my point. While it's possible to have "undecidable problem" included here, I'd rather see something moved from here to there. Tizio 16:53, 12 February 2008 (UTC)
 * What do you think of the slight rearrangement of this article I tried this afternoon? — Carl (CBM · talk) 17:44, 12 February 2008 (UTC)
 * Excellent!!! Your change really clarifies the difference between the definition of decision problems and its possible classifications. Tizio 18:07, 13 February 2008 (UTC)
 * I see you’ve created sections on Decideability and Complete Problems, with links to main articles. That seems a better arrangement; would that be the outcome of the merger proposal? It seems better than bringing that stuff over to here. On the same note, is there a case for merging "List of UP" into "UP"? Or trimming those sections of "UP" and linking to "List"? Moonraker12 (talk) 18:23, 14 February 2008 (UTC)

 * No, they're not the same thing - a decision problem is a problem with a yes/no answer, and is a basic object studied in complexity and computability theory. It's not the same thing as a decidable problem, which is an effectively computable problem as studied in computability theory. Unless you plan to enumerate and explain the many possible classifications for decision problems here, a merge is inappropriate - better would be to briefly mention some classifications and link to relevant articles on decidability and undecidable problems. Dcoetzee 09:55, 14 February 2008 (UTC)

 * Whatever organization we choose of these topics, it's fairly weird that Decidable language and Undecidable language redirect to different articles. Pichpich (talk) 17:36, 19 February 2008 (UTC)
 * Actually, I just realized that Decidable problem and Undecidable problem redirect to distinct articles. There's a lot of nonsense in the organization of these articles because different classes of mathematicians have historically used different terminologies to refer to the same object.
 * Do we really need distinct articles for Recursively enumerable language and Recursively enumerable set? Sure, there are cosmetic differences but the two articles could be merged and present a more intelligent discussion of the very slight distinction.
 * Same question: why keep distinct articles for Recursive set, Recursive language, Decidable language (which for some weird reason redirects to Decision problem)?
 * Why keep distinct articles for Undecidable problem and Undecidable language when all modern textbooks treat decision problems and languages as de facto equivalent notions? Do we need a separate article for computable function?
 * If we keep all these articles without going through a few merges, a lot of work will have to be done twice to improve and expand the content. We can always keep the redirects in the relevant categories, which should make everyone happy. Pichpich (talk) 20:16, 20 February 2008 (UTC)
 * I would be fine with some merges provided the article titles are neutral - Recursive languages and sets, Computable sets and languages, or something like that. Computable function seems fine; recursive function is a disambiguation page. It would be worth announcing merges at both the computer science and mathematics wikiprojects (I'm affiliated with the latter). — Carl (CBM · talk) 22:16, 20 February 2008 (UTC)
 * Yup, probably important to manage susceptibilities by picking a neutral, if slightly awkward title and by letting everybody know. Perhaps it is best to construct both Recursive languages and sets and Computable sets and languages first (I mean without redirecting the other pages to it) and then gather opinions about whether this makes more sense. I'm willing to give a hand. My background is theoretical CS so if math people want to help out, that would be great. Pichpich (talk) 22:22, 20 February 2008 (UTC)
 * Experiment now under way. I've created Recursive languages and sets. Let's see if we can find a smart way to do this. Pichpich (talk) 22:29, 20 February 2008 (UTC)

Side note: another absurd content fork is Word problem (computability). For one thing that terminology has almost entirely gone out of style and is almost solely used either in its group theoretical sense (word problem for groups) or its generalization to monoids, quasigroups or magmas. As mentioned earlier, all modern textbooks have (wisely) decided to identify a formal language with its associated decision problem. So Word problem (computability) should be merged back to Decision problem. Pichpich (talk) 22:44, 20 February 2008 (UTC)
 * Ick. I thought that article was the one about the word problem for groups, from the title. If there is a merge afoot, that article should definitely be included. — Carl (CBM · talk) 23:17, 20 February 2008 (UTC)

Since Recursive languages and sets actually contains sections about undecidable problems, I believe it should be rather named Decidability or something like that. An equivalent solution is to have this article only discuss decidable problems while keeping undecidable ones in a separate article. Tizio 10:09, 21 February 2008 (UTC)
 * It would need to be Decidability (computability) or something like that, because there is already Decidability (logic) on a different subject; Decidability redirects to a disambig page. But I like Decidability (computability), because it's punchy and neutral. — Carl (CBM · talk) 13:35, 21 February 2008 (UTC)
 * Actually, Decidability (logic) is about the decidablity of the problem of whether a logical formula is in a given set (e.g., whether a first-order formula is satisfiable); it's the application of the concept of decidability to logical decision problems. A summary of it could be included (with a link, as per Summary style), in a section of Decidability. Tizio 15:08, 21 February 2008 (UTC)
 * Yes, that's a good idea. — Carl (CBM · talk) 16:38, 21 February 2008 (UTC)

---

From Kleene 1952 creates a rather precise "decision tree" with regards to what constitute a "decision method", "decision procedure" and a "calculation method". He begins with the notion of ". . . general questions, such that any particular instance of the question can be answered by a preassigned uniform method. More precisely, in such an example, there is an infinite class of particular questions, and a procedure in relation to that class, both being described in advance, such that if we thereafter select any particular question of the class, the procedure will surely apply and lead us to a definite answer, either "yes" or "no" to the particular question selected." He gives a couple examples e.g. #2: "Does the equation ax + by = c, where a, b, c are given integers, have a solution in integers for x and y? There is a well-known method for answering the question, using Euclid's algorithm." Then he proceeds with his "decision tree" as follows : "A method of this sort, which suffices to answer, either by "yes" or by "no", any particular instance of a general question, we call a decision procedure or decision method or algorithm for the question. The problem of finding such a method we shall call the decision problem for the question. The problem appears in modern logic with Schroeder 1895, Lowenheim 1915 and Hilbert 1918 . . . we shall attempt a more precision definition of what constitutes a decision method later . . .. ¶ Similarly, we may have a calculation procedure or algorithm (and hence a calculation problem) in relation to a general question which requires for an answer, not "yes" or "no", but the exhibiting of some object."(Kleene 1952:136, boldface added)

As some decision problems are provably decidable (Kleene gives the example of a theorem re how to determine if two logical equations from the propositional calculus are equivalent: i.e. construct the truth table), and some are not, and given these definitions and clarifications, I conclude that the article should not be merged. I suggest the flag be removed.

RE a plethora of perhaps-redundant articles: Is there some sly way of determining all articles that fall into this class of interest (mathematics, algorithm, decision method, calculation method, logic, decision paroblem(s), undecidable problems, etc) and then structuring them and eliminating+redirecting those that are redundant? Or do we just let them proliferate and then use the whack-a-mole method in an ad hoc manner? Bill Wvbailey (talk) 17:23, 25 January 2009 (UTC)

too weasly for wiki?

 * However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an NP-complete problem and its co-NP-complete complement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.

Maybe expand or at least point to some references? — Preceding unsigned comment added by 97.81.29.81 (talk) 01:03, 10 July 2012 (UTC)

Contents of Entscheidungsproblem talk page
In case the decision is made to go ahead with merging the Entscheidungsproblem page into the Decision problem article, here are the archived contents of that page. At least some of this might be useful to incorporate into the article. — Objectivesea (talk) 02:03, 12 November 2014 (UTC)

Origin of the Entscheidungsproblem (taken from history on Turing machine page)
The origin of the Entscheidungsproblem goes back to Gottfried Leibniz. In the late 1600's, after having constructed a successful mechanical calculating machine, Leibniz dreamed of building a machine that could manipulate symbols in order to determine the truth values of mathematical statements (Davis 2000:3-20). He realized that the first step would have to be a clean formal language, or what he called a lingua characterica. Much of his subsequent work was directed towards that goal but had no lasting influence. In fact, George Boole, without knowledge of Leibniz' work (cf Gratten-Guiness and Bornet 1997:xliii), devised a "calculus" of logic (ironically not accepting the possibility of the logical OR X+X = X discovered by Leibniz (Davis 2000:18) and yet proposing X*X = X; Stanley Jevons subsequently argued with Boole for the acceptability of the logical OR (Gratten-Guiness and Bornet 1997:xiv)).

Then in 1879, Frege presented his " Begriffsschrift, a formula language, modeled upon that of arithmetic, for pure thought". About this Frege states: "'In fact, what I wanted to create was not a mere calculus ratiocinator but a lingua characterica in Leibniz's sense.' (van Heijenoort 1967:2)." Bertrand Russell and Alfred North Whitehead subsequently reworked Frege’s peculiar symbolism into a more "user friendly" format that would appear in 1914 as Principia Mathematica. This, together with Guiseppe Peano’s axioms of arithmetic (1899) would, through the efforts of many mathematicians over the next 30 years, evolve into the langua characterica that Leibniz had sought.

1901: Russell’s Paradox
In 1901 Bertrand Russell sent a letter to Frege, pointing out a problem with Frege's logic by creating a simple paradox, now called Russell's paradox. It represented a problem that simply refused to go away and would, 30 years later, bring down David Hilbert's "program" to reduce all of mathematics to symbol-manipulation.

1905: Richard's Paradox
[Unlike the Russell paradox which involves "sets", but like the Barry paradox, this is a paradox of language, and the use of language. Very simple to state. Careful examination makes the reader Rather uncomfortable because of hidden assumptions and little errors in its original form (a letter). Makes use of Cantor's diagonal argument. Problem of language addressed only cursorily by Finsler (1926) but in great depth (i.e. central argument) by Gödel (1931). "Both Godel's and Finsler's arguments, with their similarities and differences, skirt the Richard paradox without falling into it; both exploit Richard's argument to obtain new and valid conclusions" (van heijenoort 1967:439).

1900: The Entscheidungsproblem (the "decision problem") expressed in Hilbert's tenth question
In 1900 the famous mathematician David Hilbert posed a set of problems -- now known as Hilbert's problems – his beacon illuminating the way for mathematicians of the twentieth century. The 2nd problem asked for a proof that “arithmetic” is “consistent”. Kurt Gödel would prove in 1931 that, within what he called “P” (nowadays called Peano Arithmetic), “there exist undecidable sentences [propositions]” (Gödel in Davis 1965:6, in van Heijenoort 1967:596). Because of this, “the consistency of P is unprovable in P, provided P is consistent”(Gödel’s theorem IX, Davis 1965:36). While Gödel’s proof would display the tools necessary to resolve the Entscheidungsproblem, he himself would not answer it for reasons described below.

It is within the tenth problem where the question of an "Entscheidungsproblem" actually appears, but the question would float about for almost 30 years before it was framed precisely. (The tenth problem itself was resolved in the negative in 1970; its resolution in turn required the tools developed to answer the Entsheidungsproblem). Hilbert's original description is as follows:

"'10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability . . . The Entscheidungsproblem must be considered the main problem of mathematical logic. . .. The solution of the Entscheidungsproblem is of fundamental significance for the theory of all domains whose propositions could be developed on the basis of a finite number of axioms' (this translation, and the original text in German, appears in Dershowitz and Gurevich 2007:1-2)."

By 1922, the specific question of an "Entscheidungsproblem" applied to Diophantine equations had developed into the more general question about a “decision method” for any mathematical formula, and H. Behmann stated that the ". . . most general form of the Entscheidungsproblem [is] as follows: A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion. . ." (Gandy 1994:57, quoting Behmann)

"Behmann remarks that . . . the general problem is equivalent to the problem of deciding which mathematical propositions are true." (Gandy 1994:57)

Martin Davis explains it this way: Suppose we are given a "calculational procedure" that consists of (1) a set of axioms and (2) a logical conclusion written in first order logic, that is -- written in what Davis calls "Frege's rules of deduction" (or the modern equivalent of Boolean logic). Gödel's doctoral dissertation (1930) proved that Frege's rules were complete "...in the sense that every valid formula is provable" (van Heijenoort, p. 582). Given that encouraging fact, could there be a generalized "calculational procedure" that would tell us whether a conclusion can be derived from its premises? Davis calls such calculational procedures "algorithms". The Entscheidungsproblem would be an algorithm as well. "In principle, an algorithm for [the] Entscheidungsproblem would have reduced all human deductive reasoning to brute calculation" (Davis 2000:146).

In other words: Is there a “decisional algorithm” that can tell us if any algorithm is "true" (i.e. an algorithm that always correctly yields a judgment "truth" or "falsehood"?)

” . . . it seemed clear to Hilbert that with the solution of this problem, the Entscheidungsproblem, that it should be possible in principle to settle all mathematical questions in a purely mechanical manner. Hence, given unsolvable problems at all, if Hilbert was correct, then the Entscheidungsproblem itself should be unsolvable" (Davis 1967:108). Indeed: What about our Entscheidungsproblem algorithm itself? Can it determine, in a finite number of steps, whether it, itself, is “successful” and "truthful" (that is, it does not get hung up in an endless “circle” or “loop”, and it correctly yields a judgment "truth" or "falsehood" about its own behavior and results)? Within this question Russell's paradox (and Cantor’s diagonal argument) is reasserting itself with a vengeance.

1926: Finsler's (arguable) first demonstration of an undecidable proposition
[Requires understanding of the Richard paradox (1905). Finsler rightly shows the undecidability of a provable statement (known to be false outside the system) rather the undecidability of a true or a false statement. [insert Godel quote here from his 1970]. Godel trashes Finsler's argument in an unpublished letter (1970). [insert nasty Godel 1970 here to make point that the matter involves a "system system"].others (Hilbert and Bernays 19xx) were (somewhat) accepting, goobut when Finsler attempted to claim priority Godel brushed him off [insert quote here from Breger 1992: "Finsler strives for truth in mathematics, not just for formal derivability" (p. 255) "According to Hilbert and Bernays (1939...; compare also Bernays 1935...) the central idea of Finsler's paper is remarkable and should be given due respect, but his contention is merely analogous to Godel's theorem, and his reasoning cannot be put to use by proof theory" (p. 257)], his proof lapsing into oblivion. van Heijenoort 1967 and more recent commentators yield conflicting/confusing opinions. ]

1928: Hilbert further defines the Entscheidungsproblem
By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete...? Second, was mathematics consistent? Third . . . was mathematics decidable?" (Hodges p. 91, Hawking p. 1121).

Hodges describes it this way: "By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete in the technical sense that every statement. . . could be proved, or disproved. Second, was mathematics consistent, in the sense that the [false] statement ‘2 + 2 = 5’ could never be arrived at by a sequence of valid steps of proof. And thirdly, was mathematics decidable?" By this he meant, did there exist a definite method which could, in principle, be applied to any assertion, and which was guaranteed to produce a correct decision as to whether that assertion was true.” (Hodges 1983:91).

1931: True ≠ Provable: Gödel's undecidability theorem VI (the so-called "first incompleteness theorem")
The "first incompleteness theorem" appears as "Theorem VI" in his 1931 paper On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. In Gödel's original notation, it states:

"The general result about the existence of undecidable propositions reads as follows: "Theorem VI. For every ω-consistent recursive class κ of FORMULAS there are recursive CLASS SIGNS r, such that neither v Gen r nor Neg(v Gen r) belongs to Flg(κ) (where v is the FREE VARIABLE of r).2 (van Heijenoort translation and typsetting 1967:607. "Flg" is from "Folgerungsmenge = set of consequences" and "Gen" is from "Generalisation = generalization" (cf Meltzer and Braithwaite 1962, 1992 edition:33-34) )

In 1930-1 Kurt Gödel, by the proof of his undecidability theorem IV and the consequences thereof (in particular Theorem XI, the second so-called "incompleteness theorem"), answered the first two questions NO. But in order to do this he had to first demonstrate an undecidable assertion (sentence, proposition).

The approach that Gödel took is simular to that taken by Finsler (1926). First, like Finsler, he does not employ the assertion "x is [or is not] true" but rather, he employs "x is [is not] provable". Second, like Finsler he employs Cantor's diagonal method (although his usage is subtle whereas Finsler's is obvious).

"Some form of diagonalization argument lies at the basis of most proofs, or perhaps of every proof, of the undecidability theorm and of the first incompleteness theorem..."(Franzen 2005:70)

Indeed, in this context the diagonal argument is used by Gödel (1931), Church (1934), Turing (1936-7), and Kleene (1952).

Third, unlike Finsler, Gödel expresses his assertions "x is [is not] PROVABLE" within a tightly-defined system of arithmetic, i.e. a tiny collection of symbols, axioms and formation rules that define "the numbers" and the total functions of common arithmetic (e.g. "add", "multiply", "raise to a power", "divide" etc). So just what does PROVABLE mean?

"A formula is provable if a proof of it exists" (Godel 1934:p.41)

Gödel's notion of "a proof" is not what the student learns in geometry. In his "proof" the last axiom or "formula" must follow "immediately from" (as an "immediate consequence" of, ) the preceding axiom(s) and/or formula(s):

"A finite sequence of formulas shall be a proof (specifically, a proof of the last formula of the sequence) if each formula of the sequence is either an axiom, or an immediate consequence of one or more of the preceding formulas" (Godel 1934:p.41). This definition is difficult. It contains many hidden (tacit) assumptions/definitions such as "sequence", "last", "immediate consequence", "preceding". But unlike Finsler, Gödel attempts to clear these issues up in his "rigorous execution of the proof" (Gödel 1934 as the quote appears in Davis 1965:9), or as translated by van Heijenoort "with full precision" (p.599).

For Gödel a "formula" is a sequence of axioms or a sequence of formulas or a combined sequence of axioms and formulas. So as shown in the example below for "CLEAR x" (x is a register, CLEAR means "empty" or "make equivalent to zero"), the "formula" is actually a sequence of axioms with numbers substituted for the variables. Similar formulas can be written for any arithmetic or logic formula such as "ADD_TO_A B", "LOAD_A_WITH C", "STORE_A_IN B", "AND_TO_A B" etc. But even Godel's axiomatic treatment has "tacit" axioms:

"In other words, the know-how of a human being is necessary -- a know-how which is not formalized in the axioms...It seems to me that Hilbert...was also aware of this fundamental problem of an axiomatic approach.... Evidentally the know-how which is necessary to understand a certain piece of written formal logic is usually hidden" ((cf Berger Tacit Knowledge and Mathematica knowledge 2000:227-228). Godel's formulas and the scheme he used to convert them to numbers is complex. A simpler example might be useful. Perhaps from it we can to see what Godel was up to, and to see if, and if so where, any other tacit assumptions are hiding.

A very simple, but very powerful, computational "system" is the Turing-equivalent counter machine, an abstract computational model that we call "M". This M should behave like primitive recursion, that is, work from a tiny set of 5 "number-theoretic formulas/formation-schemata (word used by Godel 1931:12 in U, also Kleene 1952:219). The following is Kleene's list (1952:219) and a similar list was used by Godel:

The Kleene list:

(I) successor function (II) constant function (III) identity or "projection" function (IV) definition by substitution (V) definition by primitive recursion (2 types, the first one similar to Godel's that starts from 0th case and is over one variable) The Godel list: ≡≠⇒⋀⊗ℵ↑∆←⊆∉∈∸→⊂∀∃ℕ∩∪ǎăℬ⇔

(I) Peano axioms: 0 exists and has no successor, IF x' = y' THEN x = y, primitive recursion starting from the 0th case and is over one variable). (III) The 4 base axioms of Principia Mathematica (III) Substitution (V) identity or projection function: (∃u)(∀v (u(v)≡ a)). A function u exists, such that for all formulas v used in formula u, the formula v ≡ a can be plucked out of the bunch of them. Here a is a formula that does not contain u free, and I am using modern symbols ∃ and ∀ and modern usage. "This axiom represents the axiom of reducibility (comprehension axiom of set theory)" (ibid p. 13) [what is this axiom ??] (VI) Type-elevation: x1 ∀ (x2(x1) ≡ y2(x1) --> x2 = y2

"This axiom asserts that a class is completely determined by itself" (ibid p. 13) "c is an immediate consequence of" a and b (of a) if a is the formula (~b)V(c), where c is the formula ∀v(a) <= ?? Our machine will be the Melzak model (holes in the ground), but simplified to the Lambek model (the abacus model, cf B-B-J 2002:45ff), and further modified into the Peano axioms (see Minsky 1967:201, also Shepherdson-Sturgis ??): A line of holes (aka "registers") begins with a hole (of potentially unbounded size) labelled 1, an unlimited source S of pebbles to be put into the holes, and a mechanism that is capable of following a set of instructions in a TABLE with respect to the holes and pebbles. The holes in the ground are the "variables" and will be of only type I. The numbers are the collections of pebbles in the ground. The set of instructions that the mechanism follows will be:

(1) Constant function: CLR_A [should I use the indirection method? CLRi]: : clear a hole called "1" of pebbles (aka hole "A") (2) Successor function: INC_A [should I use the indirection method? INC_A]: add a single pebble to the hole labelled "1" (3) Identity function: ldAi, MOVrAi, CPYrAi[here I have to use the indirection method]: From the entire sequence of holes, find the hole, the number of which, is the quantity of pebbles in hole "2" (aka P) Use this procedure. remove all the pebbles from the hole labelled "2" (aka "P" for "pointer"). Start with hole 1 and put the pebbles in one-to-one correspondence with the holes until the pebbles run out: the hole where this happens is the hole of interest. (4) Substitution function: stAi In a manner similar to ldAi, find the hole of interest. Then remove all the holes from pointer-hole #2 (aka P) [either throw them into the pointed-to hole, or count out a similar number from the source S and throw those into P; replace the counters into hole A (aka #1). CPYAri ?? (5) Recursion function and mu-operator combined (see Minsky 1967: After each instruction the following will occur. Also, there is a specific IF-THEN operation JZ as follows: Test hole #1 to see whether or not said hole is empty of pebbles. If empty go to the instruction marked "[A]=Z" else go to the "[A]≠Z". OR: two holes J1 and J2... no, still must either go to next instruction

The Universal program: The TABLE of instructions for U must know the exact construction of the program-instruction set, where its dedicated registers reside, and where the starting program-instruction will be. Note that the program-instruction set need not be the same as the TABLE-instruction set; in fact, in our example it will not be.

Godel's second restriction, a rather onerous one, is as follows. Because diagonalization arguments (and Godel's argument) operate only on "functions of a single variable" (Godel 1934:Undecidable p.46), the model must be modified so we can create only single-variable formulas. This, as we see below, forces us into defining sequences of recursive formulas. Gödel commented on why this is possible in a "Remark: Variables for functions (relations) of two or more arguments are superfluous as primitive symbols since one can define relations [functions] as classes of ordered pairs [etc]..."(Davis translation 1965:10).

Another outcome of this second restriction will be the following: "Formulas" (that is, sequences of axioms or other formulas) must have one entry-point "at the top", and one exit-point "at the bottom." Godel's (very important) "immediate consequence" formula #43 Fl(x, y, z) ("Fl" from "Fogle" i.e. "consequence" (cf Meltzer-Braithwaite 1962:33) makes use of a similar notion. To say that a formula "x is an immediate consequence of formulas y and z" means that EITHER (1) y=z implies x OR (2) there exists some bound-variable "v" and x = v for function y "generalized over variable v". [THIS ISN'T QUITE RIGHT BUT ITS CLOSE]. The term (1) takes care of axioms and term (2) takes care of some preceding formula y. But the point is that either y=z --> x or y&z --> x ( (z & z-->y) & (y & y-->x) => x ).

The Cantor diagonalization method requires that all the axioms for all their possible parameters (i.e. CLEAR 1, CLEAR 2, ... CLEAR N, INCREMENT 1, INCREMENT 2, ... INCREMENT N, etc) and all the possible "formulas" such as ADD_TO_A B", "LOAD_B_FROM C", "MULTIPLY_A_BY M", "STORE_A_IN P" etc must be "enumerable" -- convertable to numbers and countable, to boot.

Given that Gödel was able to display “undecidable sentences [propositions]”, Gandy can now answer the question posed above about what happens when we submit our Entscheidungsproblem algorithm to itself for testing:

”For any such system Σ Gödel constructs a formula φ which is satisfiable, but for which this fact cannot be proved in Σ. As a consequence, given any proposed algorithm α for the Entscheidungsproblem and any system Σ, either it cannot be proved in Σ that α always gives an answer, or it cannot be proved in Σ that its answer is always correct.” (Gandy 1994:63)

So why didn’t Gödel just go ahead and prove the undecidability of the Entscheidungsproblem? Gandy supposes that first “one needed to reflect long and hard on the idea of calculability” (Gandy 1994:64). The ever-cautious Gödel was unconvinced that either Church’s λ-definability or even his own forms of "recursion" (primitive recursion in Gödel 1931, eventually augmented into “Herbrand-Gödel” recursion by the mid-1930's) was adequate to the task. Besides, the question requires finite means, and Gödel was more interested in “nonfinist concepts and methods” (Gandy 1994:64). So, the third question — the Entscheidungsproblem — would have to wait until the mid-1930's.

1931-1935: Effective calculability: λ-calculus? Recursion? Machine computation?
The problem was: An answer to the Entscheidungsproblem first required a precise characterization – a definition, an hypothesis/conjecture, or better yet, an axiomization -- of the notion of "definite general applicable prescription" or what Alonzo Church would come to call "effective calculability (cf part "7. The notion of effective calculability" in Church 1936:100 in The Undecidable). Even the form of the characterization – should it be a definition, or a hypothesis, or an axiomization? – would come under debate.

In 1928 no such characterization existed. But over the next 6–7 years Princeton professor Church and his two students Stephen Kleene and J. B. Rosser would propose a "definition" by use of Church's λ-calculus and Herbrand-Gödel’s recursion theory -- i.e. Gödel's primitive recursion modified by a suggestion of Jacques Herbrand. Then Emil Post would propose his so-called “working hypothesis” (of a worker moving from room to room writing and erasing marks per a list of instructions) (Post 1936), and lastly a few months later (1936-7) Alan Turing would follow up with his proposed "a- (automatic) machine" (closer to an axiomization but still not considered by some to be fully axiomatized, cf Gandy 1980, Sieg 1998, Moschovakis 2001, Dershowitz and Gurevich 2007).

1935: Church’s proof
Indeed, Church's paper (presented to the American Mathematical Society 19 April 1935, published 15 April 1936) showed that an undecidable problem did exist. Church states the purpose of his paper this way:

”The purpose of the present paper is to propose a definition of effective calculability2 which is thought to correspond satisfactorily to the somewhat vague intuition notion. . . and show, by means of an example, that not every problem of this class is solvable.” In footnote 2, Church states that “definition of effective calculability can be stated in either of two equivalent forms, (1). . . if it is λ-definable, (2). . . it is recursive in the sense of [Herbrand-Godel modified by Kleene]" (U. p. 90). Furthermore in this definition he uses the criterion “the algorithm has terminated becomes effectively known” (U p. 100).

An explanation of Church’s example is beyond the reach of this article. Gandy explains (cf Gandy 1994:81-2) that within all the undecidability proofs (Church’s, Kleene’s and Turing’s) the method involves (1) Enumeration -- An algorithmic-like method to list all possible well-formed functions F of a single variable m, assign a number to m, convert each parametrized-function “F of m” Fm to a Gödel number G(Fm), and put the G(Fm) in numerical order; (2) A successful demonstration that each parameterized-function Fm (and as a consequence its Gödelization G(Fm)) is a total function, i.e. to match the Gödelized G(Fm) to the correct Gödelized answer G(n), (3) Use of Cantor’s diagonal method to derive a contradiction when the function F is the decision procedure D acting on its own number i.e. G(D(D)) =? G(“True”? or “False”?).

Within the year Church would go on to strengthen his result, and in a paper titled A Note on the Entscheidungsproblem (April 1936) he would show that:

“The general case of the Entscheidungsproblem 7 of the [logical] system L is unsolvable.” ”7. The Entscheidungsproblem of a system of symbolic logic is here understood [in the sense of what is called the "deducibility problem" below, that is, as] the problem to find an effective method by which, given any expression Q in the notation of the system, it can be determined whether or not Q is provable in the system. Hilbert and Ackerman (loc. cit) understand the Entscheidungsproblem of the engere Funktionenkalkül [first order functional calculus] in a slightly different sense. But the two senses are equivalent in view of the proof by Kurt Gödel and the completeness of the engere Funktionenkalkül. . . .” (brackets in the original, Church 1936 :’’The Undecidable’’ p. 113) Church sees two forms of the question: (i) “a constructive proof of the unsolvability of what we may call the “deducibility problem” of the engere Funktionenkalkül, that is the problem to find an effective procedure which is capable of determining, about any given expression in the notation of the engere Funktionenkalkül, whether it is decidable in that system; (ii) “. . . a procedure for determining universal validity, [that] depends upon the non-constructively proved theorem of Gödel that every universally valid expression is deducible in the engere Funktionenkalkül, as well as on the assumption of the converse of this, that every deducible expression is universally valid.”

Church wondered : Had he proven case (ii) beyond a doubt? His proof relies upon Gödel’s completeness theorem (i.e. his PhD thesis, not his so-called incompleteness theorems), and Church noted (and Davis reiterates on 1965:108-109, and in 2000:114-5) that this is a “non-constructive” proof i.e. it relies on the use of reductio ad absurdum and consequently, the Law of Excluded Middle, an anathema to mathematicians with an intuitionistic outlook.

1931-1937: A flurry of activity
Church beat Alan Turing to the punch by almost a year (Turing's paper received 28 May 1936, published January 1937).

Without knowledge that Church-Kleene-Rosser at Princeton had been working on the same problem, Turing, a Master's student at King's College, Cambridge UK, was approaching his characterization of "effective calculability" from a much different angle. And, the appearance of Church’s proof spurred Emil Post to publish; he too had been working in obscurity for a number of years, and he quickly submitted a brief paper in the fall of 1936 that offered as his "working hypothesis" of "effective calculability" a “process” (a man moving through a sequence of boxes marking and erasing per a list of instructions) very similar to Turing's a-machine. Moreover in a footnote he took a poke at Church's notion of a "definition" for effective calculability: Church’s definition would “mask this identification under a definition [and hide] the fact that a fundamental discovery in the limitations of the mathematicizing power of Homo Sapiens has been made and blinds us to the need of its continual verification.” (Footnote 8, Post 1936:291 in The Undecidable). Although Turing’s submission of his paper (received 28 May 1936) gave him a few months' priority over Post, Post's paper published first and Church had to certify that Post's work was independent of Turing's. Church and Paul Bernays refereed Turing's paper from spring 1936 through the fall; Bernays found errors in Turing's last proof and Turing had to modify it. But this gave Turing time to study Church's paper and add, in August 1936, an Appendix where he sketched a proof that Church's λ-calculus and his a-machines would compute the same functions.

Church would in turn defend himself against Post’s criticism by suggesting that “to define effectiveness as computability by an arbitrary machine subject to the restrictions of finiteness would seem to be an adequate representation of the ordinary notion, and if this is done the need for [Post’s] working hypothesis would disappear.” (cf Church 1937 in Gandy 1994:79).

"But what Church had done was something rather different, and in a certain sense weaker . . . the Turing construction was more direct, and provided an argument from first principles, closing the gap in Church's demonstration." (Hodges p. 112).

1936-7 Turing’s Proof
Most of Turing's paper describes "effective calculability" in terms of "computable numbers are those whose decimals are calculable by finite means" (p. 117), in other words, his a-machines. He sets up an enumeration to be done by his universal machine U; it provides a “circle-deciding machine D” with numbers to test for “circularity”, starting with “1” and continuing in numerical sequence, (i.e. in modern terms, each number represents a programs to be tested for “unending loops”). He then proves, first, that his universal enumerator/circle-deciding program H = U+D cannot decide whether H (i.e. itself) will or will not end in "a circle" (a never-ending loop). (By assumption: it must never loop, but rather it must go on testing forever. But when it tests itself, its actions are to start with 1 and proceed, number by number, to test each one – by definition this is a circle and violates the premise.) By use of this result, Turing then proves that no universal deciding program E can tell if any machine M "ever prints a given symbol (0 say)." Armed with this second proof he goes on to prove that:

”The Hilbert Entscheidungsproblem can have no solution. . . there can be no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.” (U. p. 145)

Explanation of this proof is beyond the scope of this article. It involves Gödelizations of “complete configurations” of a-machines and subsequent attempts to match them to Gödelized “answers”, with failure as the ultimate outcome.

1936-1965: Post’s "working hypothesis"
In his 1936 paper Post only proposed his "working hypothesis" of “a process” and criticized Church's "definition", but had proved nothing. rather, Post maintained a more philosophic stance. He hoped to publish a series of "wider and wider formulations . . . The success of the program would for us, change this hypothesis not so much to a definition or to an axiom but to a natural law" (Post 1936:291 in The Undecidable)

In later years Post remained skeptical of Church’s definition of effective calculability (Kleene’s “Thesis I” of 1943, named “Church’s Thesis” by Kleene in 1952) and Turing’s a-machines (named “Turing’s Thesis” by Kleene in 1952). In a paper Post submitted in 1941 and had rejected (subsequently published in 1965 by Davis in The Undecidable) he ponders the notion of, and the nature of, undecidability:

“1. The phrase “absolutely unsolvable” is due to Church. . . [but} this true only with respect to a given logic. A fundamental problem is the question of the existence of absolutely undecidable propositions, that is, propositions which in some a priori fashion can be said to have a determined truth-value [that is, either “true” or “false” but not both simultaneously], and yet cannot be proved or disproved in any valid logic" (Post in Davis 1965:340)

He seems to make a distinction between "number theory problems" of "Church" and what he called "combinatory mathematics" (cf Post 1965:338). Indeed, Post is emphatic about “the fundamental importance to mathematics of the existence of absolutely unsolvable combinatory problems. . . .“ He suggests that by use/adoption of “recursiveness” as a criterion of solvability, “the unsolvability in question as in the case of the famous problems of antiquity, becomes merely unsolvability by a given set of instruments. . . . The fundamental new thing is that for the combinatory problems the given set of instruments is in effect the only humanly possible set.” (Post 1965:340)

Post was seeking not just a “formulation which includes an equivalent for every possible ‘finite process’ but rather a “description that will cover every possible method for setting up finite processes”; he described this in his part “7. Generated sets of sequences” (Post 1965:402). He acknowledges that the “Turing simplifications” may work for “analysis of process” but doubts that they will work for “analysis of proof” (cf footnote 6:343) and he wonders if “Turing’s finite numbers of mental states hypothesis” will hold up under scrutiny and whether or not “an equally persuasive analysis be found for all humanly possible modes of symbolization” (footnote 9:344). Post hoped for a “reversal of the entire axiomatic trend of the late nineteenth and early twentieth centuries, with a return to meaning and truth. Postulational thinking will then remain as but one phase of mathematical thinking” (Post 1965:345).

1965-present: Later developments
About Post’s “fundamental problem. . . the existence of absolutely undecidable propositions” mentioned above in Post’s footnote 1, Gandy remarks that:

”This was the problem he hoped one day to solve. It is a problem which most people today have stopped (alas?) thinking about.” (Gandy 1994:90) [add something here about Gandy, Sieg, Moschovakis, Gurevich et. al. all trying to "characterize" (axiomatize) the generalized notion of "computation" by man or machine, and in all forms]

--- end ---

Robin Gandy 1994, “The Confluence of Ideas in 1936”, pages 51-102 in Rolf Herken (ed) 1994-1995, The Universal Turing Machine: A Half-Century Survey, Second Edition, Springer-Verlag/Wien New York, ISBN 3-211-82637-8. Nachum Dershowitz and Yuri Gurevich, "A Natural Axiomatization of Church's Thesis", 2007, http://research.microsoft.com/~gurevich/Opera/188.pdf)

Another major rewrite. wvbaileyWvbailey 18:18, 7 August 2007 (UTC)

 * There is something wrong with the section "The Entscheidungsproblem of 1928:" Mathematics is generally believed to be consistent, and although the proof systems for first order logic are complete, the axioms of mathematics are incomplete in a different sense. I have not looked at the sources to see how they present it, but as it is stated that para needs some help. — Carl (CBM · talk) 23:17, 6 August 2007 (UTC)

 * I agree. I had a bad time with the one sentence about Godel. Have I struck out the offender?

In 1930 Kurt Gödel answered the first two questions: YES the first order logic was complete (Gödel’s doctoral thesis proved his completeness theorem), but NO: the notion of primitive recursion (i.e. the arithmetic of Peano axioms and first order logic) was inconsistent (it could be used to “pose” a question about itself that could be answered in both the negative and the affirmative). Tonight I found a good quote in Gandy 1994 that perhaps I will substitute after reading up a bit more on this. Thanks for your look-over. wvbaileyWvbailey 04:11, 7 August 2007 (UTC)

 * Yes, striking out that part is a large improvement. Here is the current version.

 * By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete . . . Second, was mathematics consistent. Third . . . was mathematics decidable?" (Hodges p. 91, Hawking p. 1121). As mentioned above, in 1930-1 Kurt Gödel answered the first two questions: YES the first order logic was complete (Gödel’s doctoral thesis proved his completeness theorem), but NO: arithmetic’s consistency could not be answered within arithmetic (Peano Arithmetic) itself.

 * My concern is that the question "is mathematics complete" could mean "are the axioms we have chosen for mathematics strong enough to prove all mathematical truths?". This is a very different question than "is first order logic complete". It follows from both Godel's theorems and Tarski's undefinability-of-truth theorem that there is no effective (or even arithmetically definable) axiom system strong enough to completely capture the theory of the natural numbers. If you have Hodges' book, could you clarify what he means? Otherwise, I'll try to get to it, but I am busy this week. — Carl (CBM · talk) 17:58, 8 August 2007 (UTC)

 * I will study this very carefully (I've researched this a bit since your note and agree that what I wrote is misleading). I will propose new wording. Thanks, — Wvbailey 22:25, 8 August 2007 (UTC)

 * The following is the whole quote from Hodges. I've added some quotes from Godel 1931 and my interpretation of what is going on:

"By the 1928 international congress of mathematicians, Hilbert "made his questions quite precise. First, was mathematics complete in the technical sense that every statement. . . could be proved, or disproved. Second, was mathematics consistent, in the sense that the [false] statement ‘2 + 2 = 5’ could never be arrived at by a sequence of valid steps of proof. And thirdly, was mathematics decidable?" By this he meant, did there exist a definite method which could, in principle, be applied to any assertion, and which was guaranteed to produce a correct decision as to whether that assertion was true.” (Hodges 1983:91). In 1930-1 Kurt Gödel, by proof of his undecidability theorem IV and the consequences thereof, answered the first two questions NO. while it might be true that the first order logic might be complete (Gödel’s doctoral thesis proved his completeness theorem), With regards to “completeness”: Godel demonstrates that Peano arithmetic P is powerful enough to express, in P itself (he shows how to do this in footnote 360), the metamathematical statement “Arithmetic P is consistent". But as a consequence of his "undecidability Theorem" IV, “the SENTENCE which asserts that x [an arbitrary recursive consistent class] is consistent is not x-provable; in particular the consistency of P is unprovable in P, provided P is consistent (in the contrary of course, every statement is provable)”(Gödel’s theorem XI, Godel 1931:36 in The Undecidable). Thus in Peano arithmetic P there exists at least one statement that cannot be proven “consistent” or “inconsistent”; this fact makes P incomplete. But worse, just as the theorem states, the statement P is consistent cannot be proved within P itself. So in effect, Gödel got “two for one”. I need to read up on this more, compare translations, etc. But this is a stab at it. — Wvbailey 03:05, 10 August 2007 (UTC)

Importance
I've changed the importance of this page from "low" to "mid". Actually, I think it rates a "high", but philosophers who are not mathematicians may think differently. The subject of the page is the impossibility of deciding every question that can be posed. Rick Norwood 19:39, 7 September 2007 (UTC)

 * I'm neither mathematican nor a philospher and I think it could be mid-to-high, at least from a (mathematics) foundational and historical perspective. In particular it has application to the philosophy of mind (that's the secret reason for my interest). Some writers fault the philosphers for not understanding the issues at gut-deep level but nevertheless concocting dubious pronouncements and arguments (e.g. not understanding quantum mechanics re philosophy of mind; also all the examples in Torkel Franzen 2005 Godel's Theorem: An Incomplete Guide to this Use and Abuse, A K Peters, Ltd. Wellesley MA). Another reason is: all three proofs of the 1930's that were so significant -- Church 1936, Turing 1936-7, Kleene 1943 -- all revolve the unsolvable "decision problem", and they all use similar techniques to arrive at their proofs (conversion of proofs to numbers, their subsequent enumeration (listing) and Cantor's diagonal argument). Godel 1931 (his theorem VI, the so-called first incompleteness theorem) is also a proof of undecidability and follows a similar tack. Is any of this of use to philosphers constructing arguments? I dunno, but I would hope so. wvbaileyWvbailey 21:52, 7 September 2007 (UTC)

Lack of mention of Tarski's theorems
I am very disappointed that there is no mention, either in the article or this talk page, of Alfred Tarski's theorems (in 1936) that truth is undefinable (see Indefinability_theory_of_truth). Hccrle (talk) 01:24, 1 October 2009 (UTC)

 * After reading this I consulted Grattan-Guiness (2000) The Search for Mathematical Roots 1970-1940 pp. 551-553. I see some interesting stuff, but nothing about his contributions to the Engscheidungsproblem, nor about "truth is undefinable". In fact, Tarski's truth is definable by going outside the formal system (theory) into the metasystem (metatheory); Grattan-Lewis in fact gives Tarski credit for the names "metalanguage" and "metatheory). To make the point, Grattan-Guiness gives the example directly from Tarski: '"it is snowing" is a true sentence if and only if it is snowing'" (Tarski 1936a, 156)(cf Grattain-Guinness 200:552). Bill Wvbailey (talk) 18:42, 1 October 2009 (UTC)

Reference to Whitehead and Russell
What has the reference to Whitehead and Russell at the end of the article got to do with the subject matter? 213.122.67.212 (talk) 12:52, 6 November 2010 (UTC)

 * The "vicious circle" paradoxes and the Entsheidungsproblem derive from the same problem of self-referencing propositions, i.e. impredicativity. The article is pretty thin and doesn't get into this. BillWvbailey (talk) 13:46, 6 November 2010 (UTC)

 * The negative solutions (Church's and Turing's) of the Entsheidungsproblem were found by a kind of self-reference (though that's not a phrase I'd use), but Hilbert's Entsheidungsproblem didn't (I shall boldly claim) derive from "self-reference". 213.122.62.19 (talk) 17:35, 11 November 2010 (UTC)

Negative solution[
This section states: "Turing reduced the halting problem for Turing machines to the Entscheidungsproblem."

 * I don't think this is accurate. Turing & Church showed that deciding provability of arithmetic statements could be used to decide the Halting Problem, which really means that the Entscheidungsproblem was reduced to the halting problem and not the other way around? — Preceding unsigned comment added by Froskoy (talk • contribs) 08:28, 5 February 2013 (UTC)

Date of Turing's paper
I have fixed the incorrect date on Turing's 1936 paper. The footnote at the end of Bob Soare's 1996 paper "Computability and Recursion": [www.people.cs.uchicago.edu/~soare/History/compute.pdf] has a good explanation of the correct dates. The reprint of Turing's paper in the collection edited by Martin Davis, (which was referenced before) only says that the reprint is from ser. 2, vol. 42 (1936-7), pp. 230-265, so I don't think the previous explanation of the date is justified from that book. As far as I can tell, the dating is incorrect in MathSciNet, (explaning many people incorrectly referencing the paper from 1937), but it is correct in Zentralblatt. — Preceding unsigned comment added by 131.215.108.224 (talk) 21:32, 1 May 2013 (UTC)

Merger proposal from Entscheidungsproblem
It's rather bizarre to me — although I'm by no means a mathematician — that English Wikipedia has both a page entitled Entscheidungsproblem and a second page entitled Decision problem, a page which has a German version entitled Entscheidungsproblem. I think the best solution might be to merge the two pages into one. Not sure which should go where, but it might be easier to merge Entscheidungsproblem into Decision problem, since that page is currently the larger of the two. Interestingly, both pages were begun way back in August 2001 and have had some of the same early contributors.

For 13 additional non-English Wikipedias, this poses a problem as well. Catalan, Czech, Spanish, Farsi, French, Croatian, Italian, Portuguese, Russian, Serbo-Croatian, Swedish, Ukrainian and Chinese all have articles on both topics, similar as they may be. The French, in fact, distinguish between two articles Problème de la décision and Problème de décision — by using a definite article in the title of one of them. On the other hand, Bengali, German, Korean, Hebrew, Kannada, Dutch, Japanese, Polish and Thai only link to Decision problem, whilst Arabic, Latin and Simple English link to Entscheidungsproblem — Objectivesea (talk) 01:14, 12 November 2014 (UTC)
 * A decision problem is a very general concept in computational complexity having almost nothing to do with formal logic. The Entscheidungsproblem (also called "the decision problem") is an instance of a decision problem arising in formal logic and having almost nothing to do with computational complexity theory. I don't think these make any sense for merging, merely because of the coincidence of nomenclature — see WP:NOTDICT. Therefore I have removed your ill-advised merge tags. After reviewing the two articles, I also moved some material from one article to the other to make the separation clearer. At this point there is not even any mention of either article in the other one. We could probably solve this better with a hatnote. The German WP still does mix up the two concepts but that's their problem, not ours. —David Eppstein (talk) 03:53, 12 November 2014 (UTC)

 * Thanks for clarifying this, Dr. Eppstein. I defer to your knowledge, and I appreciate your setting me straight.

 * In the light of the extreme similarity of article titles in at least some languages, however, might it be a good idea, perhaps, to set up a disambiguation page for each of Decision problem and Entscheidungsproblem, since, according to my Cassell's German dictionary, the two vocabulary terms literally — although not, apparently, mathematically — mean the same thing? Then we could have the two present articles renamed to Decision problem (computer science) or Decision problem (computation). The other article could be renamed to Entscheidungsproblem (logic). This sort of change might also be of assistance to the German Wikipedians, who would now be able to create a second article specifically on the decision problem using a title in their language like Entscheidungsproblem (Logik).

 * I don't think it would be a big problem to then correct the pointers using the "What Links Here" tool. I'd be willing to do this and to make sure that no existing links were broken, if you thought this might be a good idea. Best regards, Erik Pedersen (Objectivesea). — Objectivesea (talk) 05:38, 12 November 2014 (UTC)
 * Disambiguation pages are usually only used when there are more than two subjects with the same name. Here we have only two, so the usual solution is a hatnote (which I have added). (Also, I'm not sure "computer science" is right, and "computation" is also not quite right — recursion theory is usually considered more part of mathematics than CS, I think.) —David Eppstein (talk) 06:00, 12 November 2014 (UTC)

 * Thanks again for this elegant solution, Dr. Eppstein. I think it's something that could be adopted also for those languages where the possibility for confusion may still persist. I'm planning to translate a few introductory paragraphs from some of these articles for the Esperanto Wikipedia (a language which seems to really strive to avoid potential ambiguity). I greatly appreciate your bearing with me in my efforts to gain more clarity, and you have surely provided this. — Objectivesea (talk) 07:31, 12 November 2014 (UTC)

Cleanup
I changed the hatnote to "otheruses4" to be more clear about what kind of output is intended. The "about" template can make many kinds of output, but this article is intended to use the one produced by "otheruses4". I also changed the ISBN magic links syntax to use the new ISBN template, because ISBN magic links will be disable sometime soon. I think it is clearer to use "template:" in these. — Carl (CBM · talk) 23:19, 15 April 2017 (UTC)
 * Ok, but what is the reason for including all those "template:" namespace things in your templates? The whole point of putting things into template space is that you can then use them as templates without having to specify the namespace. —David Eppstein (talk) 00:09, 16 April 2017 (UTC)
 * You can use them either way - both methods are completely equivalent from the point of view of the software. For the ISBN templates in particular, I think it is helpful to emphasize that the template version is being used instead of the magic link. I am starting to think that the longer version may be more clear in general. I have been working my way through the computability theory category looking for cleanup and expansion opportunities, and converting the ISBN magic links as I go. — Carl (CBM · talk) 00:14, 16 April 2017 (UTC)

Definition
According to the Encyclopedia Br.: "decision problem, for a class of questions in mathematics and formal logic, the problem of finding, after choosing any question of the class, an algorithm or repetitive procedure that will yield a definite answer, “yes” or “no,” to that question. The method consists of performing successively a finite number of steps determined by preassigned rules. In particular, the term is used for such procedures for finding whether—in a particular logistic system, logical calculus, or formal mathematical system—some given “well-formed formula” (generated in accordance with established formation rules) is or is not provable as a theorem of the system."

not the question is the decision problem, but the search for an algoritm. Madyno (talk) 22:13, 18 August 2022 (UTC)
 * If you have a question, or a suggestion for improvement of the article, your writing makes it unclear. In any case, a problem and a method for solving the problem are two different things. —David Eppstein (talk) 22:42, 18 August 2022 (UTC)
 * As I'm not familiar with decision problems, I hope to hear comments on what I found. Furthermore it would be clearer if it is explained why the set of inputs need to be infinite. Madyno (talk) 09:57, 23 August 2022 (UTC)

Decision problem picture misleading
The picture included in the article is misleading at best. If the decision problem is undecidable then no such algorithm exists, however the universe of discourse is still partitioned by question. For example, every Turing machine either halts or it does not, this gives a partition of the set of all Turing machines into halting and non-halting, even if there is no general way of deciding if a machine belongs in the halting set. — Preceding unsigned comment added by Gillchild (talk • contribs) 06:41, 7 February 2024 (UTC)

title: Talk:Decision problem


text:
Detroit River

The Detroit River flows west and south for 24 nmi from Lake St. Clair to Lake Erie as a strait in the Great Lakes system. The river divides the metropolitan areas of Detroit, Michigan, and Windsor, Ontario—an area collectively referred to as Detroit–Windsor—and forms part of the border between Canada and the United States. The Ambassador Bridge, the Detroit–Windsor Tunnel, and the Michigan Central Railway Tunnel connect the cities.

The river's English name comes from the French Rivière du Détroit (translated as "River of the Strait"). The Detroit River has served an important role in the history of Detroit and Windsor, and is one of the world's busiest waterways. It is an important transportation route connecting Lake Michigan, Lake Huron, and Lake Superior to Lake Erie and eventually to Lake Ontario, the St. Lawrence Seaway and the Erie Canal. When Detroit underwent rapid industrialization at the turn of the 20th century, the Detroit River became notoriously polluted and toxic. Since the late 20th century, however, a vast restoration effort has been undertaken because of the river's ecological importance.

In the early 21st century, the river today has a wide variety of economic and recreational uses. There are numerous islands in the Detroit River, and much of the lower portion of the river is part of the Detroit River International Wildlife Refuge. The portion of the river in the city of Detroit has been organized into the Detroit International Riverfront and the William G. Milliken State Park and Harbor. The Detroit River is designated both an American Heritage River and a Canadian Heritage River—the only river to have this dual designation.

Geography
The Detroit River flows for 28 mi from Lake St. Clair to Lake Erie. By definition, this classifies it as both a river and a strait — a strait being a narrow passageway connecting two large bodies of water, which is how the river earned its name from early French settlers. However, today, the Detroit River is rarely referred to as a strait, because bodies of water referred to as straits are typically much wider relative to their length. The river forms the southern portion of the waterway connecting Lake Huron to the north and Lake Erie to the south, with other portions including the St. Clair River and Lake St. Clair.

The Detroit River is only 0.5–2.5 mi wide. It begins with an east-to-west flow from Lake St. Clair, but curves and runs north to south. The deepest portion of the Detroit River is 53 ft in its northern portion. At its source, the river is at an elevation of 574 ft above sea level. The river is relatively level, dropping only 3 feet before entering Lake Erie at 571 ft. As the river contains no dams and no locks, it is easily navigable by even the smallest of vessels. The watershed basin for the Detroit River is approximately 700 sqmi.

Since the river is fairly short, it has few tributaries, the largest being the River Rouge in Michigan; this is four times longer than the Detroit River and contains most of the watershed. The only other major American tributary to the Detroit River is the much smaller Ecorse River. Tributaries on the Canadian side include Little River, Turkey Creek, and the River Canard. The discharge for the Detroit River is relatively high for a river of its size. The river's discharge averaged over the year is 5300 m³/s, and the river's flow is relatively constant.

The Detroit River forms a major element of the international border between the United States and Canada. The river on the American side is all under the jurisdiction of Wayne County, Michigan, and the Canadian side is under the administration of Essex County, Ontario. The largest city along the Detroit River is Detroit, and most of the population along the river lives in Michigan. The Detroit River has two automobile traffic crossings connecting the United States and Canada: the Ambassador Bridge and the Detroit–Windsor Tunnel. Both of these are strongly protected by the U.S. Customs and Border Protection and the Canada Border Services Agency.

The upper portion of the river is one of the two places where a Canadian city lies directly south of an American city. In this case, the city of Detroit is directly north of the city of Windsor, Ontario. The only other location where this occurs is Fort Erie, Ontario, which lies south of several cities in Niagara County, New York. The cities and communities southwest of Detroit along the American side of the river are popularly referred to as the Downriver area, because those areas are said to be "down the river" from Detroit. Several of these communities do not border the Detroit River but the term "Downriver" refers broadly to the cluster of 18 suburban communities that lie to the southwest of the city of Detroit and to the west of the Detroit River.

Islands
The Detroit River contains 31 charted islands. The majority of the islands are located on the American side of the river. Many of the islands are small and uninhabited, and none are divided by the international border, as the two countries do not share a land border along the river. Grosse Ile is the largest and most populated of all islands, and Fighting Island is the largest Canadian island. Most islands are located in the southern portion of the river.

History
Europeans first recorded navigating the Detroit River in the 17th century. The Iroquois traded furs with the Dutch colonists at New Amsterdam by traveling through the Detroit River. The French later claimed the area for New France. The famed sailing ship Le Griffon reached the mouth of the Detroit River in mid-August 1679 on its maiden voyage through the Great Lakes. Later, when the French began settling in the area, they navigated the river using canoes made of birch or elm bark. Handcrafted vessels were a common mode of travel across the river, and pirogues and bateaux were also used.

As the North American fur trade intensified, European settlers expanded their trade westward into uncharted territories. French explorer Antoine Laumet de La Mothe, sieur de Cadillac sailed up the Detroit River on July 23, 1701. The next day, he established Fort Pontchartrain du Détroit, which developed as Detroit. The French named the river as Rivière Détroit. Détroit is French for "strait". The river was known literally as the "River of the Strait".

When Great Britain defeated the French in the Seven Years' War (known as the French and Indian War on the American front), it took over control of the Detroit River, as well as other French territory east of the Mississippi River. The newly formed United States claimed this territory during the American Revolution, but the British did not transfer it until 1796.

During the War of 1812, the Detroit River served as a major barrier between the American Michigan Territory and British Upper Canada, especially during the Battle of Fort Detroit in August 1812. Detroit briefly fell to the British. After the completion of the Erie Canal in 1817, which opened up easier travel to Lake Erie from the East Coast of the United States, connecting the Great Lakes to the Hudson River and the port of New York City, the Detroit River became a route for many migrating settlers traveling to northern Michigan. Detroit rapidly attracted a share of new residents. Following the Patriot War, in which British regulars and Michigan militia nearly came to armed conflict on the ice-covered Detroit River, the United States built Fort Wayne at Detroit to counter Britain's riverside Fort Malden at Amherstburg across the river.

The Detroit River served as a final stop on the Underground Railroad and was the most active entry point along the United States–Canada border for fugitive slaves.

Escaping slaves often chose to cross through the Detroit River rather than flee to Mexico because of the river's location near free states made it less risky than traveling through slaveholding states that border Mexico. The strong Underground Railroad networks in the Canadian border region also assisted Blacks hoping to flee from the U.S. once the Fugitive Slave Act was strengthened in 1850. Canada also granted legal immigration status to Blacks, while Mexico did not for many years.

Individuals and organizations assisted escaping slaves hoping to cross the Detroit River from the United States into Canada. The Second Baptist Church of Detroit and First Baptist Church of Amherstburg coordinated ferrying thousands of Blacks across the Detroit River into Canada, and Detroit's Colored Vigilant Committee assisted over 1,500 fugitives in crossing into Canada. Famous abolitionists and Underground Railroad conductors including George DeBaptiste and William Lambert worked individually and with these organizations to assist fleeing slaves and condemn slavery.

There was considerable transnational fluidity between the Canadian and American sides of the river until the middle of the 19th century. The 1833 Blackburn Riots in Detroit, which erupted after slave hunters detained couple Lucie and Thornton Blackburn, marked the end of hundreds of years of a nearly porous border between Canada and the United States on the Detroit River. Detroit's African American population protested and helped the Blackburns escape across the Detroit River to Upper Canada, where the British colonial government in Canada declared former slaves could not be extradited to be returned to their owners. With their freedom in Canada secured, crossing the Detroit River out of the United States became an imperative for escaping slaves.

During the American Civil War (1861–1865), the Union feared the seceded Confederate States of America (CSA) would plan a northerly attack from Canada, which was controlled by the British Empire and remained neutral in the war. The Union feared the CSA would cross the Detroit River to launch this attack. For that reason, Union forces regularly patrolled the Detroit River and the fortification at Fort Wayne improved, although it was far removed from any major combat. A Confederate plot to capture the U.S. Navy warship, USS Michigan, and liberate Confederate prisoners from Johnson Island, in western Lake Erie, was narrowly averted only after the Confederates had captured two passenger steamships.

At the beginning of the 20th century, Detroit's industrialization took off on an unprecedented scale. The Detroit River became the world's busiest commercial river and in 1908 was dubbed "the Greatest Commercial Artery on Earth" by The Detroit News. In 1907, the Detroit River carried 67,292,504 tons (61 billion kg) of shipping commerce through Detroit to markets all over the world. By comparison, London shipped 18,727,230 tons (16 billion kg), and New York shipped 20,390,953 tons (18 billion kg).

Prohibition
From 1920 to 1933, the United States (US) enforced the Prohibition era. The sale, manufacture, and transportation of alcohol for consumption were nationally banned. Detroit, as the largest city bordering Canada, where alcohol remained legal during Prohibition, became the center of a new industry known as rum-running, smuggling liquor into the US.

No bridges connected Ontario, Canada and Michigan, US, until the Ambassador Bridge was finished in 1929 and the Detroit–Windsor Tunnel in 1930. Smugglers used boats of varying sizes to transport alcohol across the river during the summer, and during the winter months, rum-runners traveled back and forth across the frozen Detroit River by car. In some cases, overloaded cars fell through the ice. In the 21st century, car parts from this era are occasionally still found on the bottom of the river. Rum-running in Windsor and production of bootleg liquor became common practices. American mobsters such as the Purple Gang of Detroit used violence to control the route known as the "Detroit-Windsor Funnel," and continue to gain lucrative returns from the trade. The name parodied the newly built tunnel between the cities and nations. The Detroit River, Lake St. Clair, and the St. Clair River are estimated to have carried 75% of all liquor smuggled into the United States during Prohibition. Government officials were unable or unwilling to deter the flow.

The rum-running industry died when prohibition was repealed in 1933 by the Twenty-first Amendment.

Submerged objects
Because of the booming businesses and long history of Metro Detroit and Windsor, Ontario, the Detroit River has been the site of many artifacts, some lost with sunken ships and others abandoned, such as murder weapons or stolen bronze statues. A DMC DeLorean has also been recovered from the river. The artifacts recovered are well preserved due to the river's fresh water but low visibility makes them difficult to find.

A 1940s-era bronze statue depicting a classical nude woman was originally installed to overlook a reflecting pool in the Grosse Pointe War Memorial. It was nicknamed "The Nude," and, in 2001, was believed to have been successfully stolen for display in some art collector's private cache. During a police diving exercise near a submerged Jeep, the statue was found in 2009, restored, and returned to the memorial.

Anchors from the SS Greater Detroit, a luxury steamship that toured the Detroit River from 1924 to 1950, and the famed SS Edmund Fitzgerald, a lake freighter that sank in a terrible 1975 storm, have notably both been recovered from the river. The 6,000-pound anchor of the SS Greater Detroit was raised in November 2016. It was installed at the Detroit/Wayne County Port Authority Building. The lost anchor of the SS Edmund Fitzgerald was recovered during a July 1992 project, and the anchor was installed in the yard of the Dossin Great Lakes Museum on Belle Isle.

Since the 1980s, divers have recovered a total of six 1700s-era cannons from the river. The last was found in 2011 near the Cobo Center. They are believed to have been part of the pre-War of 1812 inventory kept by the British garrison in this area. Historians believe another three cannon may still be in the river. Inventory documents record a total of 17 cannons and 14 have been accounted for. It is believed that the British dragged the cannons onto the frozen river so they would sink with the spring thaw, and be kept from use by the American enemy. Another seven, larger cannons may have fallen off a barge closer to Amherstburg, Ontario, and may yet be found in the river.

Pollution and conservation efforts
Much of the land that surrounds the Detroit River is urbanized and, in some places, has been used for industrial purposes for more than 100 years. There has been excessive water pollution of the river from the long-term, unregulated dumping of chemicals, industrial waste, garbage, and sewage. Much of the Detroit River and its shoreline were polluted and unsafe for recreational use. Thousands of migrating birds died each year because of the oil slicks and contaminated water around the mouth of the Detroit River at Lake Erie. The river's oxygen levels were depleted to the point where fish could not inhabit its waters. Because this pollution often drained into and affected Lake Erie, the lake was considered "dead" and unable to support aquatic life.

In 1961, a congressional order founded the Wyandotte National Wildlife Refuge. That began the government's placing tighter restrictions on industries; substantial government funding at various levels has been allocated to clean up the river. In this early period, opponents believed that such efforts would adversely affect Detroit's industry and economy. In 1970, toxic levels of mercury in the water resulted in the total closing of the fishing industry in the St. Clair River, Lake St. Clair, the Detroit River, and Lake Erie. Finally, a massive conservation effort was initiated to clean up the Detroit River. For years, the multi-million dollar cost of removing pollutants from the river and the political influence of nearby industries, hindered conservation efforts.

In 1998, the Detroit River was designated as an American Heritage River by the US Environmental Protection Agency and in 2001 as a Canadian Heritage River. It is the only river in North America to have such dual designations.

In 2001, the Wyandotte National Wildlife Refuge was absorbed into the larger Detroit River International Wildlife Refuge, a cooperative effort between the United States and Canada to preserve the area as an ecological refuge. The millions of dollars spent since that time to dredge pollutants out of the Detroit River has led to a remarkable restoration, although problems remain. Today, many species of native animals that had been driven out by human development are returning to the area. The river is home to a growing number of bird species such as eagles (including reintroduced bald eagles), ospreys, and peregrine falcons. Large numbers of lake whitefish, sturgeon, silver bass, black bass, salmon, perch, and walleye are again thriving in the river.

The Detroit River and its recovery efforts were listed as a Michigan State Historic Site in 2007. A historic marker was erected along the river in a park that now serves as the Detroit River International Wildlife Refuge visitor center in the city of Trenton.

Economy
The Detroit River is used for shipping and trading. The earliest use of the river for these economic activities was the shipping of furs for trade as early as the 17th century. By the time the fur trade decreased, Michigan had begun to exploit the lumber-rich areas of Northern Michigan and the Upper Peninsula. Detroit turned into a major industrial region, largely because of the Detroit River. The only way a ship could travel out of the upper Great Lakes system was to travel down the Detroit River. From there, ships could travel anywhere in the world out of the St. Lawrence Seaway or the Erie Canal to New York City. At the beginning of the 20th century, the automotive industry boomed, and the many manufacturers imported abundant supplies of iron ore, sand, limestone and wood.

The Detroit River provides substantial revenue for the local economies. A 1991 study showed $20.1 million came from sales related to waterfowl hunting along the Detroit River. The same year, bird watching, photography, and other non-consumptive uses of waterfowl contributed another $192.8 million to Michigan's economy. Local economies benefit through boating registrations and fishing licenses. It is estimated walleye fishing alone brings in $1 million to the economy of communities along the lower Detroit River each spring. Other fish caught by recreational fisherman include white bass, bluegill, crappie, freshwater drum, smallmouth bass, northern pike and muskie. There are over 800,000 recreation boats in Michigan, and more than half of them are regularly used on or near the Detroit River. Popular river destinations in Detroit include the Detroit International Riverfront and Belle Isle Park — both of which host events throughout the year. Several restaurants on the river have docks for boaters. Tour boats and dinner cruises travel through the sights of Detroit and the undeveloped islands downriver. Cruise ships support tourism on the Great Lakes and dock at the Port Detroit passenger terminal downtown. The iconic Renaissance Center is on the banks of the Detroit River.

Bridges and crossings
According to a 2004 study, 150,000 jobs and $13 billion in annual production depend on the river crossings connecting Detroit to Windsor. In 2004, the American trade with Ontario alone was $407 billion, in which 28% ($113.3 billion) crossed the Detroit River.

There are two automobile traffic routes that completely cross the river: the Detroit–Windsor tunnel and the privately owned Ambassador Bridge, both of which connect Detroit, Michigan, to Windsor, Ontario. A railway tunnel and a commercial truck ferry service also travel between Detroit and Windsor. In Michigan, there are two bridges connecting the mainland to Grosse Ile, as well as the MacArthur Bridge that connects the mainland Detroit to Belle Isle. All ports of entry on the American side are secured by the U.S. Customs and Border Protection, and the Canadian side is secured by the Canada Border Services Agency; all areas between the American ports of entry and on the American side of the river are secured by the United States Border Patrol.

The Gordie Howe International Bridge is a new bridge project which began construction in 2019; it will directly connect Highway 401 in Canada to Interstate 75 in the United States.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Detroit River


text:
Dsungaripterus

Dsungaripterus is a genus of dsungaripterid pterosaur which lived during the Early Cretaceous in what is now China and possibly South Korea. Its first fossil was found in the Tugulu Group (Lianmuqin and Shengjinkou Formations) of the Junggar Basin.

Description
Dsungaripterus weii had a wingspan of 3 - 3.5 m. Like most dsungaripteroids it had a rather robust skeleton with thick walls and stouty bodily proportions, suggesting a mostly terrestrial lifestyle. The flight style of these animals is unclear, but it was probably punctuated by abrupt landings and extensive flapping.

The skull of Dsungaripterus, measuring over 46 cm long, bore a low bone crest that ran down from the base of the skull to halfway to the beak. Dsungaripterus's head and neck were together almost 1 m long. Its most notable feature are its long, narrow, upcurved jaws with a pointed tip. It had no teeth in the front part of its jaws, which were probably used to remove prey from cracks in rocks and/or the sandy, muddy inland environments it inhabited. It had knobbly flat teeth more to the back of the jaw that were well suited for crushing the armor of shellfish or other hard objects. Thus, it is commonly interpreted that dsungarupterids were durophagous and possibly piscivorous pterosaurs. Additionally, Dsungaripterus also had a palate similar to that of azhdarchoids.

History of discovery
Dsungaripterus was described in 1964 named by Yang Zhongjian. The genus name combines a reference to the Junggar Basin with a Latinized Greek pteron, "wing". The type species is Dsungaripterus weii, the specific name honoring paleontologist C.M. Wei of the Palaeontological Division, Institute of Science, Bureau of Petroleum of Xinjiang. The holotype is IVPP V-2776, a partial skull and skeleton from the Lianmuqin Formation. In 1973, more material has been found within the Shengjinkou Formation, which includes almost complete skulls.

In 1980 Peter Galton renamed Pterodactylus brancai (Reck 1931) from the Tendaguru Formation into Dsungaripterus brancai, but the identification is now commonly rejected. In 1982 Natasha Bakhurina named a new species, Dsungaripterus parvus, based on a smaller skeleton from Mongolia. Later, this was renamed into "Phobetor", a preoccupied name, and in 2009 concluded to be identical to Noripterus. A dsungaripterid wing finger phalanx was reported in 2002 from the Hasandong Formation of South Korea, and was identified in 2015 and 2018 as Dsungaripterus? cf. D. weii.

Classification
Dsungaripterus was classified by Yang as a member of the Dsungaripteridae. Below is a cladogram showing the results of a phylogenetic analysis presented by Andres and colleagues in 2014. They recovered Dsungaripterus within the clade Dsungaripteromorpha (a subgroup within the Azhdarchoidea), more specifically within the Dsungaripteridae, sister taxon to Domeykodactylus. Their cladogram is shown below.

In 2019, a different topology, this time by Kellner and colleagues, was published. In this study, Dsungaripterus was recovered outside the Azhdarchoidea, within the larger group Tapejaroidea, sister taxon to Noripterus. The cladogram of the analysis is shown below.

title: Dsungaripterus


text:
Talk:David A. Huffman

Untitled
Great entry :) -- sodium

Thanks, Can someone post his Date of Birth? I'm NOT sure if it's 1925 !!! He died on the 7th of October, 1999 though. That's for sure (100% accuracy, from UC archives) -- Saghmos

Google-searching, some of the text seems to have been copied from http://www.ucsc.edu/currents/99-00/10-11/huffman.html, are you sure you have got permission for this? -- sodium

Photo
I have a photo that David gave me years ago. I think he would like it to be the one on his Wikipedia entry: http://www.thunder-monkey.com/david_huffman-lg.jpg

I have no idea how to put it into the article. — Preceding unsigned comment added by 75.36.249.35 (talk) 23:35, 15 October 2011 (UTC)

Can someone please help out who knows how to post the picture? — Preceding unsigned comment added by 75.36.240.37 (talk) 17:10, 15 November 2011 (UTC)

"Survivors"
I don't get why this information is so important to be in Wikipedia:

''David Huffman passed away at the age of 74 after a 10-month battle with cancer. He is survived by his wife, Marilyn Huffman, of Santa Cruz; his former wife, Jane Ayres Huffman; their three children, Elise, Linda, and Stephen Huffman, all of Santa Cruz; a son-in-law, Jeff Grubb, of Santa Cruz; a stepdaughter, Marti Homer Kehlet, of Sacramento, her husband, Daret, and their daughter, Karsen; a stepson, Darin Homer of Prunedale, his wife, Jane, and their son, Ryan; and a brother, Donald Huffman, of Westerville, Ohio, his wife, Jean, and their family.''

IMO it should be removed from the article.

"History"
The History section on the Huffman Coding page contradicts what is given here (and seems to be correct). --weemadarthur 198.152.14.67 (talk) 10:04, 19 March 2009 (UTC)

Copyvio
Some of this article is copied from. Snippet search on google confirms that other text is copied from. (See ) --Moonriddengirl (talk) 00:23, 5 July 2011 (UTC)
 * I reported the issue to Moonriddengirl. I'm working on a rewrite, not finished yet. See Talk:David A. Huffman/Temp. -- SchreyP (messages) 21:53, 12 July 2011 (UTC)
 * Current temp version good enough to be merged with old article. For more details and potential new copyvio, see Copyright problems/2011 July 5. -- SchreyP (messages) 21:52, 17 July 2011 (UTC)

External links modified
Hello fellow Wikipedians,

I have just modified one external link on David A. Huffman. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20110629195033/http://www.fi.edu/winners/show_results.faw?gs=&ln=&fn=&keyword=&subject=&award=LEVY+&sy=1923&ey=1999&name=Submit to http://www.fi.edu/winners/show_results.faw?gs=&ln=&fn=&keyword=&subject=&award=LEVY+&sy=1923&ey=1999&name=Submit

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

Cheers.— InternetArchiveBot  (Report bug) 13:15, 5 September 2017 (UTC)

title: Talk:David A. Huffman


text:
David Huffman

David Oliver Huffman (May 10, 1945 – February 27, 1985) was an American actor and producer.

Personal life
Huffman was born on May 10, 1945, in Berwyn, Illinois, to Clarence and Opal Huffman (née Dippel).

Huffman married casting director Phyllis Huffman (nee Grennan) in 1967, whom he had met as a student at Webster University in St. Louis, Missouri. The couple had two sons and remained married until Huffman's death in 1985.

Huffman was an avid sailor, recreational painter, and country‐and‐western guitarist.

Murder
On the morning of February 27, 1985, 16-year-old Genaro Samano Villanueva was taken into San Diego police custody after attempting to steal a radio from a car near his home. Released into the custody of his high school vice principal, Villanueva left school and went to Balboa Park. There he was spotted by Canadian tourist Jack Beamer prowling around inside the motor home of Beamer's friends. After Beamer accosted him, Villanueva fled the scene.

Huffman, who was cast in the play Of Mice and Men at the Old Globe Theatre and was set to begin work on the television miniseries North and South the following week, had visited the theatre shortly before noon to share cookies with the cast and crew and was sitting in his van near the theatre playing his bagpipes when he saw Beamer confront Villanueva. He gave chase in his vehicle, parking the van near the Spreckels Organ Pavilion and following Villanueva into the park. When he caught up with Villanueva, the two became involved in a physical altercation, during which Villanueva stabbed Huffman twice in the chest with a screwdriver. Huffman died of exsanguination, likely within 30 to 45 seconds. His body was found less than an hour later in a Palm Canyon crevice by a group of children, although it was not positively identified until later that night.

On March 2 and 3, Crime Stoppers produced a reenactment of the crime that was shown on San Diego television and published in several national newspapers. The Canadian tourists whose motor home was burglarized saw Huffman's photo and death announcement in the newspaper and called police. Huffman was buried on March 5 at Forest Lawn Memorial Park (Hollywood Hills).

Villanueva was arrested on March 12 after a police officer recognized Villanueva from a composite sketch given to police by the Canadian tourist. On June 24, 1986, Villanueva was sentenced to 26 years to life in prison and admitted to the California State Prison, Centinela. On December 9, 2011, he was denied parole for 15 years.

Broadway stage credits

 * Butterflies Are Free as Don Baker (October 21, 1969 – July 2, 1972)

title: David Huffman