Computability Okay, we know we can't compute everything because of the halting problem, and we know that we can't prove everything because of Gödel. This is probably a silly question from a novice, but it seems the stuff we know we can't compute or prove is pretty esoteric. Are there examples or practical questions we know we can't find an answer to?
anon
I don't know if they found the answer to Fermat's last theorem.
Alardo
Yep - http://www.pbs.org/wgbh/nova/proof/
Greg Hurlman
Fermat's last theorem has been solved.
trollop
>> "Manufacturing scheduling, spare parts optimization, nuclear explosion simulation ..."
anon
Yes this did find an answer to that, I can't remember the exact details, but there was a proven logical equivanence to another problem that could be solved.
Tim H
I was taught that it is impossible to write a general computer program that can look at another computer program a say what it does.
Tim H
NP-completeness is not the same as Gödel's provability!
Karel Thönissen (www.garabit.nl)
I think the Travelling Salesman problem is a classic case here.
Nemesis
The halting problem itself is not esoteric. A program to determine whether another program completes in finite time is a very useful program! Hard realtime system, anyone?
Karel Thönissen (www.garabit.nl)
There is a big misunderstanding about Godel here. Godel is about an inherent inability to prove, logically, if a statement is true. Problems like the TSP are just about finding a method of calculating the answer that can be done in a reasonable time.
David Clayworth
Yes there's also the problem of deciding whether or not a given string belongs to a given recursively enumerable language.
Kalani
You could argue that problems relating to logic or computation are all going to be abstract to some extent. I'd say both Godel's theorem and the halting problem have practical consequences.
Matt Freestone
Yeah most (all?) of the Goedel examples are pretty contrived. This might not be quite what you're looking for, but is a good example - a problem which can't be solved using the standard axioms for set theory:
Matt
There are many simple problems that are trivially incomputable, such as the inverse of any many-to-one function.
Devil's Advocate
Oh and on the computability front - there are lots of generalisations you can get from the halting problem - eg (i think) Rice's theorem says that pretty much any non-trivial property of a computer program cannot be computed on the set of all programs. Although still a bit contrived I admit.
Matt
Um... If you're working with the definitions of 'function' and 'inverse' used in computability theory, then there /is no/ inverse of a 'many-to-one' function. Hence it doesn't make sense to talk about whether or not such a (non-existant) inverse is computable.
Matt
>> the closer it gets to being able to run Windows
Alex
Yes, look up the contiuum hypothesis.
Mathie
Stuff like uncomputability comes up every single day in programming - its why we can't make perfect automated test benches.
danielsn
Devil's advocate, what you are saying is:
Alex
Well, the original poster was looking for "practical questions we know we can't find an answer to".
Devil's Advocate
Alex, but the "pseudo inverse" of |x| is {x, -x} (a finite set) while the "pseudo inverse" of (- x x) is Z (an infinite set).
Kalani
The Busy Beaver problem may or may not map onto anything really practical, but it's the classic example of a function known not to be Turing-computable.
Thomas E. Kammeyer
OK,
trollop
The sound of one hand Flapping can be computed provided we have enough information about the size and material of the hand and the medium it's flapping in and the position of the listener.
Stephen Jones
Fog Creek Home |