On Monday, 29 July 2013 at 12:35:59 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:17:22 UTC, JS wrote:
Even something like

  if (random() == 3) break;

is decidable(it will halt after some time).

That program has a finite average runtime, but its maximum runtime is unbounded. You can't actually say it *will* halt. For any given input (in this case 0 inputs) one cannot tell whether the program will eventually halt, therefore it is undecidable.

I have formal background in CS so I might have got that totally wrong.

sorry, that should be "I have NO formal background in CS"

Reply via email to