Talk:Proof of impossibility

"Here's another clue that points to impossibility: we can describe a "machine" to do the computation as a "state machine". When the end-number is "1" then the machine halts (this is easy to construct). But can we build another machine to determine if our state machine always halts (at 1) for any arbitrary number we stick into it? No, by Turing's thesis."

I don't think this is quite right - if the Collatz conjecture has a solution, then a Turing machine CAN be built to predict the behavior of a state machine, just by using the proof of the conjecture.

The same argument can be incorrectly used to show that solvable problems are unsolvable: Consider a modified version of the Collatz conjecture, where the iterative formula is just n -> (n-1) if n > 0, and 0 -> 0. This is iterative formula is trivially proven to halt for all n>0.

To show the flaw in the argument above, we could build a state machine that halts when the number is zero, AND we could build a turing machine that trivially predicts the behavior of the state machine (using the simple fact that we know it halts if n>0).

On section "Counterexample"

I don't think that proof by counterexample is a proof of impossibility. It is just a proof of a statement of the type "not X" for some X. So I think this section should be removed.

On other words "Proof by exhaustion" is a valid method for proving negative statements, which is not mentioned. So perhaps we should include that instead.

Need content with those citations

This article has the opposite problem of most. There are sources cited for much of the information ... but the actual information is absent. Having sections tell us that a discussion of a topic in mathematics can be found in <source, p. n> does not lend itself to the WP goal of a comprehensive encyclopedia. Any chance someone with the listed sources could fill some information in? Serpent's Choice 02:56, 20 December 2006 (UTC)

My vote would be to create, where they do not already exist, sub-articles about each major topic point. My guess is more about the other articles can be found here in wiki, the only problem would be to provide the links. For example, more about the Turing first proof can be found at Turing's proof -- a difficult topic (lots of graduate-level number-theoretic math concepts) not easily summarized). More about the Ulam problem can be found at Collatz conjecture -- a very good article. Ulam/Collatz is a very difficult problem too (I've been working on it so I can attest to just how hard it is). When I get my brain disattached from the Ulam problem I will return to this page. The book by Hardy & Wright is excellent, still in print in paperback. wvbaileyWvbailey 03:50, 20 December 2006 (UTC)

Proving a negative

This issue of proof of impossibility comes up in fields other then mathematics, often as "you can't prove a negative". This article seems to focus exclusively on proof of impossibility in mathematics but I think that their should be a discussion of proving negatives as they relate to other fields of science (physics, medical science, etc.) either as a part of this article or in a more appropriate place, if this article is not deemed such. An good example that occurred to me was the issue of perpetual motion machines. Since the idea violates current understanding of the laws of thermodynamics. The problem with proving impossibility of perpetual motion machines is that one cannot prove that no exceptions or ways around the laws of thermodynamics exist and thus might someday be discovered thus leaving perpetual motion machines as a future possibility. --Cab88 17:54, 5 May 2007 (UTC)

Actually you have a good idea, but I'd suggest you create a new page, and have fun with it. The reason I find this interesting, and my take on it, ties in with the philosophic issues around Intuitionism and in particular what happens when we are confronted with an infinite domain of discourse. You will be in good company: Bertrand Russell was particularly aggrieved by the problem of "knowing" when a "truth" is true, or a "falshood" is indeed false. Whenever your "domain of discussion" is "closed", i.e. well-defined and all the elements are defined and can be investigated, proof of a negative is possible: e.g. "There are no cows in this pasture before us." But when the domain extends to the infinite or the unknown/unknowable or both, not so fast . . . "There are no cows in that pasture over the hill." Maybe, maybe not. You say your cows are all in the barn and I believe you (and we check this to be sure), but what about the neighbors' cows? We have to go over the hill to find out, and maybe a cow was in the pasture and then left before we can get there. "The sun will/will not come up tomorrow?" Maybe, maybe not. Just because it did yesterday and today doesn't mean it will/will not tomorrow. And your example of perpetual motion also brings up the idea that there are other ways to demonstrate a truth (by deductive reasoning) but this forces us to define and then accept the premises of the argument, and by what means do we finally choose to accept the premises? An early version of the Intuitionism page had an example of "flying pigs", whether they exist or not and how we would go about proving their existence or non-existence. But greater minds than mine chose to scrap the example. Turing's second proof invokes a negative that bothers me -- he had to go all the way to infinity and "invert" the null finding to make his reductio ad absurdum case. Also, your medical examples -- false positives, false negatives that sort of thing, are interesting. Communication theory confronts this same issue (tails of distributions) -- when do we accept a message, or not. When indeed do we know for (relative) certain that a truth is true and a falsehood is false? wvbaileyWvbailey 20:43, 6 May 2007 (UTC)

Abel–Ruffini theorem

The "impossibility" related to the 5th degree polynomial is generally attributed to Abel, not Galois as the intro here states. EverGreg (talk) 09:31, 23 January 2009 (UTC)

quality standards and original research

There was a section at the end of this article on the Collatz Conjecture. To me, it seems like it does not directly relate to the article or meet the other standards of wikipedia in terms of original research and general overall quality.

I believe that the section should be removed, so I've excised it and moved it to the talk page. In its place, I've created a see also section that points to the list of articles on unsolved problems in mathematics.

"== Is this simple question impossible to prove? The Collatz (3n + 1) conjecture ==

Also called Ulam's problem.

The entries above have now equipped the reader with the tools to think about an unsolved problem. Here's a chance to become famous:

"No proof of the Collatz conjecture has been found in spite of intense efforts, and the problem is generally considered extremely difficult" (Franzen, p. 11).

This is Franzen's description of the problem:

"... if we start with any positive natural number n and compute n/2 if n is even, or 3n + 1 if n is odd, and continue applying the same rule to the new number, we will eventually reach 1" (Franzén, p. 11)

Here are the first numbers. Clearly once certain numbers appear inside a string then they don't need to be "dealt with". But the lengths of the strings are interesting—they have a randomness to them that is "worrisome", per Chaitin's proof described above. This should lead us to believe that the question is "undecidable" (i.e. it's impossible to know whether the hypothesis is true or false):

1, 4, 2, 1

2, 1

3, 10, 5, 16, 8, 4, 2, 1

4, 2, 1

5, 16, 8, 4, 2, 1

6, 3, 10, 5, 16, 8, 4, 2, 1

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

8, 4, 2, 1

9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

10, 5, 16, 8, 4, 2, 1

11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

12, 6, 3, 10, 5, 16, 8, 4, 2, 1

13, 40, 20, 10, 5, 16, 8, 4, 2, 1

14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

80, 40, 20, 10, 5, 16, 8, 4, 2, 1

81, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

But here's another clue that leads us to believe that the conjecture is true: algorithms that construct numbers are sometimes thought of as "proofs" in an axiom schema. For example, "proof" in number theory has a very precise meaning—that the next "provable formula" follows from either (i) an axiom, (ii) one prior "provable formula" or, (iii) two prior "provable formulas". In order to do these proofs in the framework of a tiny set of axioms, we might think of the numbers (and the formulas themselves) as strings of "unary", just "tally marks", separated by a "blank" symbol i.e. number "7" is | | | | | | |, i.e. 7 marks. If a proof is "true" then it is a tautology. Thus the statement "3 + 4 = 7" is a tautology i.e. | | | + | | | | = | | | | | | |. (To do this we would have to express the "+" symbol and "=" symbols in a similar code, and provide adequate "formation rules" etc.) If we "check the proof" (as we used to do in geometry) by writing down all the steps that led us to the end of the proof, then the proof always ends in "True". If we assign the symbol "1" as equivalent to "True" then whenever we proof-check a tautology it always ends in 1, just as the Collatz sequence does above.

Here's another clue that points to impossibility: we can describe a "machine" to do the computation as a "state machine". When the end-number is "1" then the machine halts (this is easy to construct). State machines are "destructive" of information in the sense that we can't trace backward what they did, or exactly what path they took to arrive at where they are (unless we record all their moves). You can see that in the sequences above. If the state machine is working on "20", how did it get to "20"? We need a Turing machine to tell us.

But another argument for a proof says "how could it be otherwise?" The only possibility would be that, somehow, the number just begins to increase to infinity. Is this plausible?

And yet we know that for slightly-modified forms of the problem such as { 5*N+3, N/2 } certain numbers fall into never-ending loops. Might there be some number really big N in the { 3*N+1, N/2 } problem that also results in a loop (actually 1 --> 4 --> 2 --> 1 is how the 3*N+1 problem actually ends up if the algorithm isn't halted at 1). " — Preceding unsigned comment added by Austinfeller (talk • contribs) 03:50, 15 July 2012 (UTC)

Needing clarification

"To prove that something is impossible is usually much harder than the opposite task" - does "the opposite task" mean to prove that something is possible? A clarification is in order. — Preceding unsigned comment added by 132.72.230.71 (talk) 15:08, 22 April 2018 (UTC)

Tone

I see someone added a note about the article's tone at the top of the page. Is there any specific aspect or section of the article that has a tone issue? I can't find any overuse of jargon in the article and the mathematical language is formal and precise but not incomprehensible. Ilex verticillata (talk) 18:21, 23 October 2022 (UTC)

Might want to remove the "Tone" tag at the top then. Mathematical jargon doesn't extend very far in this text, but it might help to link more articles. Stuhlbär (talk) 12:16, 19 March 2023 (UTC)

Bible verses

Stay out of contradicting truth or using the Bible as falsehood if your using verses wrong on a couple words possible and abundance. Especially violating the ten commandments which are holy laws. This is wose then Cane and Abel, do not kill your brother on a Genesis vehicle. 170.62.21.182 (talk) 21:17, 30 May 2024 (UTC)