next up previous contents
Next: decidable doesn't mean we Up: Decidable Doesn't Mean Solved Previous: Decidable Doesn't Mean Solved

e.g. Fermat's conjecture

Fermat's conjecture is decidable, since there is only one instance of the problem. There exists a TM that accepts any input and one that rejects any input - one of these is right but it is not obvious which one [Hopcroft P. 179].



root
6/10/1998