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
for(;;)
{
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"
