Beta
×

Announcing: Slashdot Deals - Explore geek apps, games, gadgets and more. (what is this?)

### Thank you!

We are sorry to see you leave - Beta is different and we value the time you took to try it out. Before you decide to go, please take a look at some value-adds for Beta and learn more about it. Thank you for reading Slashdot, and for making the site better!

top

### A Mathematical Proof Too Long To Check

Re:prove that the program works (189 comments)

Um, excuse me. If you're going to quote me and change what I said, then indicate your edits. I have done so above, in bold. Not that I can make sense of them.

Sorry, I realized at one point I was editing the quote rather than my own text and thought I fixed it but apparently missed one of my edits and there's no reason it should make sense there. Entirely my fault.

Wha...? That's just plain wrong. I can think up all kinds of invalid proofs of the Pythagorean Theorem. But showing that a proof is invalid does not mean the theorem is incorrect. It just means your proof is.

Double wha...? I never claimed the theory behind the algorithm is incorrect, just that if an algorithm designed to produce correct proofs produces a fautly proof, the algorithm is faulty. If you think up an invalid proof of the Pythagorean Theorem, you're at fault for violating the rules of the system and I don't know why anyone would claim it's a fault of the system itself.

As for the rest, please see my other reply to your first post, relating to specific vs. universal algorithms. The gist is that a specific algorithm can be written to check the validity of this proof, but doing so is functionally equivalent to manual verification, but a universal algorithm to verify all correct proofs is impossible.

I never said that one couldn't produce either an algorithm that generates proofs or one that verifies proofs, but the fact is, since there exist true statements that are unprovable the latter algorithm cannot be universal. It can only check whether the symbols follow its understanding of the rules of manipulation.

I get what you're saying. Since Program A can be written to conform to certain rules, Program B can be written to confirm the output of A conforms to the rules that A was given, so yes the proof can be "verified" that way, but by definition you're still only covering some of the proofs A might generate.

But note that the poster I originally responded to said that the output need not be evaulated, but rather only the generating algorithm. I never even said this was a useless approach, since it will likely converge to a correct result, but it hardly counts as a proof of the result. Checking programming isn't the same as checking output, and checking output isn't the same as proving mathematical validity, though of course it can be the same as proving that what you get is what you expected to get, which may be good enough in many cases but wasn't even what I was originally responding to.

It may be that I'm assigning too much power to the algorithm that generated the proof. While it's impossible to program an algorithm with the axioms of a system and tell it to generate all the valid proofs of the system, and equally impossible to similarly program one to verify all proofs of the system, some smaller tasks (maybe this one) are certainly within the realm of algorithmic possibility. I was thinking of the original poster's comment in a very general context and not just in that of this specific problem.

top

### A Mathematical Proof Too Long To Check

Re:prove that the program works (189 comments)

Note also the poster I responded to didn't say prove the algorithm is correct and error-free, but rather that it "works," which means generates a correct proof, the checking of which (probably) invokes the halting problem. I say probably because it's likely no easier to write an algorithm that is designed specifically to check this "proof" for correctness than it is for a mathematician to verify it manually, and therefore it would be verified by a general one designed to verify proofs. The halting problem doesn't apply to the former case since it would involve a single-use algorithm to verify one single input, but it surely applies to the latter.

top

### A Mathematical Proof Too Long To Check

Re:prove that the program works (189 comments)

I think the issue here stems from the concept of "correct" and how knowable that value is.

Turing's halting problem is a statement about limitations in the ability of algorithms to examine other algorithms. Again, it doesn't mean you can't prove that an algorithm is correct, no matter how "correct" the algorithm appears.

That's kind of my point. Given this proof, it would show that the algorithm is incorrect if the proof is shown to be invalid, yet the proof is too long to be verified by anything but another algorithm, so the halting problem is definitely relevant in a discussion about algorithm-generated proofs which can't be verified by humans.

Sure, if errors are found in a generating algorithm, then they will be fixed and it will be run again, but that again doesn't show that its "proof" is a real proof without independent verification, which again invokes the halting problem if its proof is horrendously long since what it creates must be evaluated by another algorithm. There is no way to demonstrate that such an algorithm as this generates only correct proofs.

Yes, some proofs can be generated by algorithms and others can be checked by algorithms, but a mathematician is necessary at some point in the process since no non-trivial generating algorithm can be shown to create only correct proofs and no universal checking algorithm can be created which generates no false positives or negatives.

Considering how complex computer systems are, is it even possible to claim that an algorithm can run bug-free enough to consider correctness of code equivalent to verification that its output is correct in any but trivial cases?

top

### A Mathematical Proof Too Long To Check

Re:prove that the program works (189 comments)

Forgot to mention those guys showed that such an algorithm that "works" for all valid proofs is not just difficult but mathematically impossible.

top

### A Mathematical Proof Too Long To Check

Re:prove that the program works (189 comments)

Prove that the algorithm works. That's your proof.

Gödel and Turing make strong cases that proving the algorithm works for some inputs that are correct proofs doesn't count as proof it will work for all correct proof inputs. So no, even if you "prove the algorithm works" it is not the same as a rigorous mathematical proof.

top

### How To Hack Subway Fares Using Fare Arbitrage

Transfering trains in the BART system, aside from timing, is essentially arbitrary. When transfers are timed you sometimes have to wait less time to get on a different train going in the same or opposite direction, but behavior is the same. Only if the train you're getting on is the last one of the night are you required to transfer at one of those stations, and that's only because those are generally the only places they wait. Any other time of day you can transfer anywhere there are two lines together, but it will probably involve waiting. Yes, less waiting than going all the way out of one's way to a transfer station, but still (for many) too much to make the gain worth the effort.

This whole mess would only make any sense at all if timing were just such that one person's train passes another's exit station at just the right time so they could swap cards through the open door, and BART is not that predictable (though it's WAY more so than any local bus system).

top

### How To Hack Subway Fares Using Fare Arbitrage

This could maybe be done with one person (240 comments)

Back when I was poor and could barely afford public transportation when I had to use it, I thought about keeping multiple BART tickets I would use to make it look like all my longer-distance trips were actually short-distance ones that just took a long time, but I never implemented my plan. There are plenty of moral issues with stealing from a public service, but truth is those seem less important when you're a teenager with no money, but I think practicality is what ultimately prevented me from doing it.

Even if the system didn't care that a ticket was used to exit on a different day than it was used to enter (this is a big if, since BART is not a 24-hour service, making it easy to prevent such fraud), I would have to label and keep track of so many tickets and carry them with me whenever I wanted to use the train that it was really never worth it. No way was I going to get someone else involved, and the trouble of having to intentionally get off at the wrong stop sometimes was just too much trouble.

A friend of mine would just buy red children's tickets and use an x-acto knife to cut the magnetic stripe off and glue them onto standard adult blue tickets. Still stealing, still wrong, but much easier than anything suggested here.

top

### Weird Asteroid Itokawa Has a Dual Personality

Re:Summary named the sattelite wrong... (61 comments)

It's relevant to the article (very un-/.) but the poster probably didn't notice the summary is a quote or read the article (very /.) or he/she/it would have known that Hayabusa is spelled wrong in the source material. It's the journalist's job to spell-check names, not editors here. Their job is to...umm...something something...whatever, I'm sure it's very important.

top

### UT Professor Resigns Over Fracking Conflict of Interest

How can he even show his face? (190 comments)

What gets me is that the lead author has claimed (and UT seems to believe) that his conflict of interest had no impact on the quality or findings of the report. This is unlikely, but possible. I won't belabor that point. But the the only other explanation for allowing his name at the top of this nonsense is gross negligence and/or extreme incompetence, either of which should disqualify him from any academic position ever. At this point he is at best a corporate shill, and at worst an unethical idiotic corporate shill.

top

### Fetuses Caught Yawning In 4D

This is the most recent report I could find from the CDC and their numbers support the 790,000 claim, to a first approximation.

top

### German Authorities Find Al Qaeda Plans Disguised In Porn

At least in criminal trials, juries are intended to be finders of fact only, which requires no prior experience or knowledge of the relevant laws. The system was designed this way on purpose and is potentially way more equitable than a system in which someone's job/career/reputation is at stake every time he or she reaches a verdict. 12 strangers may be more emotional than a single judge, but in the long run will probably be more fair.

Nobody wants their case to be decided as soon as they find out they have the judge who thinks everyone is guilty.

more than 2 years ago
top

### Campaign Urges People To Send MPAA and RIAA Copied Currency

This reminds me of a urinal I saw recently that said its 1-pint flush saved 88% more water than standard 1-gallon urinals.

75% smaller or 150% larger = 25% or 250% of the original size
vs.
25% smaller or 50% larger = 75% or 150% of the original size (actual law)

more than 2 years ago
top

### The EFF Reflects On ICE Seizing a Tor Exit Node

I do not think it means what you think it means
Specifically, a dichotomy is a separation, usually a splitting of one thing into two separate and distinct parts. It usually requires that there be a choice, A or B.

It does not mean "hey, that's interesting."

more than 3 years ago
top

### What If Tim Berners-Lee Had Patented the Web?

I often wonder what the state of things would be if software and business method patents had been allowed 50 years earlier.

Quicksort (and others) would be patented, as would the very idea of software encryption. Codebook + on a computer = patent!

more than 3 years ago
top

### Netflix Deflects Rage Over Price Increase

Re:No rage, just a lost customer. (722 comments)

Wait, so competition increases prices for the consumer? Sometimes I wonder what the Invisible Hand is doing while I'm watching the other one take my money.

more than 3 years ago
top

### UK Authorities Accused of Inciting Illegal Protest

Not a great use of resources (371 comments)

Regarding the actions of the police under the covers, are these activities in general efficient uses of police time and taxpayer money? Why are undercover police spending seven years infiltrating environmental activists? Not terrorists, mind you, but activists. Another officer spent 4 years infiltrating an anti-racist group. Not racists, but people against racism. Really?

Seems like in seven years agents could infiltrate various government or corporate entities and expose enough graft that the program could pay for itself.

more than 3 years ago
top

### Boy Finds £2.5M Gold Locket With Metal Detector

What the locket was doing with a metal detector, I'll never know

more than 3 years ago
top

### AT&T Wireless Data Still Growing At 1000%

No, 1000% per year compounded over 3 years would be an increase of 1000 (1000% is 10 times, year 0 = 1, year 1 = 10*1 = 10, year 2 = 10 times year 1 = 100, year 3 = 10 times year 2 = 1000);

For a 30x growth in 3 years that would be an annual growth of 310%.

To calculate a yearly increase of some initial amount A at a rate of r, you would use A(1+r)
You don't just multiply the rate of increase by the initial value to get the value at the next iteration. A 100% yearly growth rate implies doubling each year, whereas in your calculation a 100% growth rate implies a static state

.

more than 4 years ago

# Submissions

top

### Jet Pack Takes Man Across English Channel

ThanatosMinor (1046978) writes "As discussed yesterday, crazy man Yves Rossy has flown over the English Channel using a jet-powered flying wing in a mere 10 minutes. From the NY Daily News article:

Yves Rossy leapt from a plane at more than 8,800 feet (2,500 meters), fired up his jets and made the 22-mile (35-kilometer ) trip from Calais in France. Rossy passed over a thin strip of land in front of South Foreland lighthouse, looped over onlookers and opened his parachute, his wings still strapped to his back.

"
top

### Lawsuit Aims to Stop LHC

ThanatosMinor (1046978) writes "Looks like the FUD is hitting the fan when it comes to the Large Hadron Collider. Apparently some people think it could destroy the earth or something. A lawsuit has been filed in Hawaii seeking an injunction that would prevent the LHC from being turned on. The LHC is the most powerful particle accelerator in the world and is scheduled to come online this year and move into full operation by early 2009."
top

### Dreamworks Drops the Ball on Afghani Children

ThanatosMinor (1046978) writes "Dreamworks recruited school-aged children from Kabul in Afghanistan to play lead roles in the new movie release of The Kite Runner. However, the presence of a brutal rape scene has serious potential to cause problems for one of the boys and his family. 'I want to continue making films and be an actor but the rape scene upset me because my friends will watch it and I won't be able to go outside any more. They will think I was raped,' said Ahmad Khan Mahmidzada. To make matters worse, two of the boys wanted to use their money from the job to move their families to the United States, but the film company paid them less than \$20,000 each.
Should Hollywood be trying a little harder to be a good ambassador to foreign nations?"
top

### Coral Reefs Dying of Herpes

ThanatosMinor (1046978) writes "Looks like many coral reefs are dying. Reefs that live in close proximity to humans tend to die, and not just from direct pollution, but also as an indirect result of global warming and overfishing allowing coral-hungry microbes to flourish. From the article, "'They're screwed no matter what we do to them,'""
top ThanatosMinor (1046978) writes "In a 5-4 decision today, the U.S. Supreme Court ruled that the EPA has the authority to regulate carbon dioxide emissions, saying that the EPA's reasons for not doing so in the past were "arbitrary, capricious or otherwise not in accordance with law." The ruling does not make any statements about whether the EPA will regulate carbon or not, but concerns about global climate change and its ties to human activity did appear to be deciding factors in the case."
top ThanatosMinor (1046978) writes "Are you a bully? Are you into shoving just for the fun of it? Did you kill a man in Reno just to watch him die? Well, researchers at the University of Michigan might have found out why. They have also shown that "while high-testosterone participants showed better learning in response to anger faces, they were unaware of the fact that they learned anything in the first place and unaware of what kind of faces had reinforced their learning."
Apparently, high-testosterone individuals' brains reward them when they see an angry face. Does this mean you can just flip someone off and see how you feel to measure your testosterone levels?"
top ThanatosMinor (1046978) writes "A Berkeley Labs press release discusses a new nickel-platinum alloy that is "10 times better than a single crystal surface of pure platinum(111), and 90 times better than platinum-carbon" to be used in hydrogen fuel cells for consumer vehicles. The prohibitively high cost of platinum is one of the things standing in the way of a practical fuel cell for everyday use in vehicles. "'Although the platinum-nickel alloy itself is well-known, we were able to control and tune key parameters which enabled us to make this discovery. Our study demonstrates the potential of new analytical tools for characterizing nanoscale surfaces in order to fine-tune their properties in a desired direction.'""

# Slashdot: News for Nerds

Mathemeticians stand on each other's shoulders while computer scientists stand on each other's toes. -- Richard Hamming