Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror

Comment Re:Problem solving (Score 1) 147

The truth is, many people feel the same way about the 100 to sometimes 1000 page proofs of some of the more complex results in mathematics. In addition to the time that experts take to review the proof, there can be some clues as to whether the proof is correct, as noted by R.J. Lipton on his blog. Foremost is the ability for the proof technique to solve related questions to the one being proven, whether they are open or not. Another one is whether the general proof technique can be understood and has not failed to solve the same problem in the past. One must remember that building a proof of a large open question is somewhat like building a house (sorry no car analogy :), you need sketches, blueprints, foundations, and only after that you start laying bricks.

More formally, it is technically possible to check a proof in polynomial time provided a formal proof has been given. This has actually been done for the proof of the 4 colour theorem, and is currently being attempted by the contender for the proof of the Kepler conjecture. Once you have a formal proof, there exists software that can check it for you, and it operates in polynomial time (if you lay aside a minor technical point which I will not go into).

Hope this helps!

Comment Re:No touchy! (Score 4, Insightful) 149

From the article:

If you tickle an orangutan, for example, it makes a series of loud panting hoots; it would be easy to mistake these sounds for pain or distress, rather than joy.

How do we know they're enjoying it and not just incapable of fighting it off like I was when I was little?

Because they -are- capable of fighting it off!

Comment Undecidable (Score 1) 223

You keep using that word. I do not think it means what you think it means ;).

More seriously, an undecidable proposition is a statement (or class of statements) for which there does not exist an algorithm (turing machine) that solves that (those) problem(s) whith 100% accuracy. One famous example is the existence of solutions to a particular Diophantine equation.

A problem that can not be proven or disproven in a particular logical theory is called independent. The existence of undecidable propositions implies the existence of independent problems: if there are no independent problems, it is easy to build a proof procedure to decide any proposition, by "simply" enumerating all possible proofs and stopping when one has found a proof or disproof of the given proposition, which will happen eventually.

Comment Re:Depends on what you mean by aiding (Score 1) 90

2) I'll paraphrase from the Tao: Though a program be but 3 lines long. Some day, someone will have to maintain it. Similarly, no matter how small a program is, it will contain bugs.

In the world of software development that the Tao refers to I have no doubt that this is true. But I have a dream... that someday my programms will not be juged by the number of their bugs but by the usefulness of their content...that someday the sons of a former logician and the sons of a former software engineer will be able to sit down together at the shell prompts of brotherhood... Also, it seems that the software that controls, say, a driverless subway system can not really afford to wait around for user reported bugs.

3) Having to go in a check the checker defeats the purpose of the checker.

Ah, the famous "Who verifies the verifier?". This question is asked in a different form in mathematical logic, where proving consistency of a formal system seems at best pointless and at worst impossible (Goedel). The point is that every proof or program verified in this system is at least as trustworthy as the proof system (or logic) itself which we hope (and almost certainly is) more trustworthy than the program we started with.

4) It isn't my job to check the checker. Nor is it any Mathematicians job to check the checker.

You are going to make a lot of Computer Scientists that work on the meta theory and the implementation of these systems very unhappy. Or are they not Mathematicians?

5) Re: well defined "A sufficiently well behaved function": You're taking what I wrote completely out of context (see (1)). Note the ()'s after that in which you quote: rigorous within context

What your comment seemed to imply is that there are mathematical texts in which objects are assumed to verify a certain number of conditions which are difficult to formalise rigorously. My point was: if it's that difficult to formalise rigorously, then it should not be in a serious mathematical text. Differential calculus was in this situation at the beginning of the XIXth century where it was unclear exactly what a "continuous function" was. It took all the genius of Augustin Cauchy (who was not himself above reproach in matters of rigour) several decades to better the situation.

I could go on...

Comment Re:Depends on what you mean by aiding (Score 1) 90

These "proof checkers" are, to put it politely, a misnomer. I find it sad that people actually think that they will work as advertised. First off, if anyone would actually look at the "code" that is needed to be entered in (at least) many of these "proof checkers" they'd realise just how problematic data entry will be.

This is completely wrong, on several points:

firstly a proof checker actually does check proofs in a very precise sense: a proof is a rigorously defined, implementable object and a proof checker verifies that this object does indeed consist of a proof of a given proposition. This is (non trivially) decidable; i.e. there exists an algorithm that carries out this task, it forms the basis of any given proof checking software called the kernel. The rest of the software is just an environment to help the user construct these formal proofs, which are checked by the kernel. As you can see, only the kernel needs to be trusted.

Secondly, as TFA states, a big difficulty with formal theorem proving is that in a formal proof, EVERY little detail has to be spelled out. This is a necessary evil for having error-less mathematical developments. The point, again stated in TFA, is that more and more of these trivial steps can and are handled automatically by the proof checking software itself. I think that what research in interactive proof systems has brought is indication that this will not need "AI that is more than a century more advanced than what we have today".

Not to mention the... numerous bugs that WILL be in the compiler and checker itself. Not to mention the impossible requirement for a zero defect environment.

From TFA:

To guard against this possibility, the designers of the proof-checking software make the "kernel" of code that implements the axioms and rules of inference as short and simple as possible.

I would like to add that these interactive proof systems are invariably open source. Why don't you go check for bugs yourself?

But, there are also many other concerns that make this a practical fools errand. Namely, how do you translate something like, "A sufficiently well behaved function" (no that's not ad hoc, it quite rigorous within context)

I would like you to try and submit an article that contains these words! If "well behavedness" is MATHEMATICALLY defined, then there is no difficulty in integrating this into a proof checking system. In any other case... good luck with publishing that article.

The only problems with correctness that come up are recent results and those are typically found quickly. It's called a retraction and it happens regularly.

Except that there are a certain number of proofs that mathematicians have a notoriously hard time trusting. The most famous example is the four color theorem, which was formalised in 2004. TFA also mentions the proof of Kepler's conjecture, there has been a fair amount of work on the huge proof of the classification of finite simple groups as well.

Formalising proofs have another important application as well: proof of correctness of computer programs. These proofs usually have the following characteristics: -They are easy: proofs of correctness do not usually rely on complex mathematics, little more than a formalisation of program semantics and elementary arithmetic are needed. - They are tedious: 10000 lines of code make for a very, very long proof. The proof will be filled with very trivial lemmas, and thousands of variations on the same argument. This makes it clear that proving correctness of programs is work that it is quite natural to partially automate. In fact much of the work on formal theorem proving has concentrated on this area. You might know this if you knew anything about formal theorem proving. Or were you suggesting that formalising classical mathematics can not possibly be useful to formalising other areas of science?

Lets not blow everything out of proportion because some clowns with nothing better to do with there time think otherwise.

In all honesty, how many of these fallacious stories are going to be published here? Because, this has been a repeated topic over the past couple weeks. Or does /. have the same technique as FOX "News"; say it enough times and it /becomes/ true?

You are actually comparing /. to fox news for interest in formal theorem proving? Would that make the logic community the Bush administration? Or are they just Clowns? Wait...

My final suggestion is this: check your facts on proof checking and RTFA.

good day sir

Slashdot Top Deals

Any circuit design must contain at least one part which is obsolete, two parts which are unobtainable, and three parts which are still under development.

Working...