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.