Article: Increasing the D Compiler Speed by Over 75%

[John Colvin]

On Monday, 29 July 2013 at 13:05:10 UTC, JS wrote:
> On Monday, 29 July 2013 at 12:36:36 UTC, John Colvin wrote:
>> 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"
>
> No, again, it isn't about infinite run time.
>
> decidability != infinite run time.
>
> to simplify, let's look at the program,
>
> for(;;) if (random() == 0) break;
>
> where random() returns a random number, not necessarily 
> uniform, between 0 and 1.
>
> Same problem just easier to see.
>
> Since there must be a chance for 0 to occur, the program must 
> halt, regardless of how long it takes, even if it takes an 
> "infinite" amount of time.
>
> That is, the run time of the program may approach infinity BUT 
> it will halt at some point because by the definition of random, 
> 0 must occur... else it's not random.
>
> So, by the fact that random, must cover the entire range, even 
> if it takes it an infinitely long time(so to speak), we know 
> that the program must halt. We don't care how long it will take 
> but just that we can decide that it will.
>
> The only way you could be right is if random wasn't random and 
> 0 was never returned... in that case the program would not 
> halt... BUT then we could decide that it never would halt...
>
> In both cases, we can decide the outcome... if random is known 
> to produce 0 then it will halt, if it can't... then it won't.
>
> But random must produce a 0 or not a 0 in an infinite amount of 
> time. (either 0 is in the range of random or not).
>
> That is, the halting state of the program is not random even 
> though it looks like it. (again, it's not how long it takes but 
> if we can decide the outcome... which, in this case, rests on 
> the decidability of random)
>
> Another way to see this, flipping a fair coin has 0 probability 
> of producing an infinite series of tails.
>
> Why?
>
> After N flips, the probability of flipping exactly N tails is 
> 1/N -> 0.

Ok, I think I get what you mean now. The 2 states of interest for 
the halting problem are, for a give input:

1) program *can* stop
2) program *will not* stop

is that correct?