edited tags
Link
Raphael
  • 70.6k
  • 27
  • 163
  • 361
Tweeted twitter.com/#!/StackCompSci/status/626855641626353664
edited tags
Link
Raphael
  • 70.6k
  • 27
  • 163
  • 361
Source Link
MaiaVictor
  • 4k
  • 15
  • 29

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. What are the simplest (smallest) known examples of such programs?