Talk:Proof of impossibility

From Wikipedia, the free encyclopedia

"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).

[edit] 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)

[edit] 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)