Article: Increasing the D Compiler Speed by Over 75%

[John Colvin]

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.