4 ms·
Yes but there are very fee practical instances of undecidable problems (by instance I mean a specific concrete here-are-the-numbers problem, not a general state
by pfortuny 8y ago
Yes but there are very fee practical instances of undecidable problems (by instance I mean a specific concrete here-are-the-numbers problem, not a general statement about “equations”).
- pas 8y agoAre there any at all? If you have exact numbers you can decide in finite time. Always, if I'm not mistaken. So, unless there is an infinity encoded in the exact problem somehow, you can always solve it by simple brute force enumeration. Look at the busy beaver, it's completely possible theoretically to simply enumerate all the possible states of a tape for a given N, and play the corresponding Turing machines. Even if calculating this is physically impossible, and proven to be impossible to generalize for any N. (That is the BB functions are uncomputable, but of course not exact values.)
- pfortuny 8y agoGödel’s sentence comes to mind. Yes, it is not “practical” but it is undecidable.
- pas 8y agoGodel's sentence is not an exact problem. It's a big number representing a claim (a theorem) about Godel numbers and the sentence itself. There's nothing to calculate there. It's a proof by construction for Godel's incompleteness theorem.