Article: Increasing the D Compiler Speed by Over 75%
JS
js.mdnq at gmail.com
Mon Jul 29 06:05:08 PDT 2013
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.
More information about the Digitalmars-d-announce
mailing list