The Value, if any, of Decidability
- Yuri Gurevich
Bulletin of the European Association for Theoretical Computer Science |
A decidable problem can be as hard as an undecidable one for all practical purposes. So what is the value of a mere decidability result? That is the topic discussed in the paper.