Article: Increasing the D Compiler Speed by Over 75%

[JS]

On Monday, 29 July 2013 at 14:39:02 UTC, John Colvin wrote:
> 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?

A program will either halt or not halt, the question is, can we 
decide. Rather:

A program will either halt or not halt, or be impossible to tell.

We'd like to think we know if a program will stop or not but we 
can't always know that... there are just some strange programs 
that we can't figure out. The program is sort of a superposition 
of halting and not halting... sort of like schrodingers cat.

For example, it is impossible to know if schrodingers cat is 
alive or dead until we open the box(but suppose we never get to 
open the box).

Here is another example:

main() { readln(); }

Does the program halt or not?

Yes! Just because it depends on what the user does, does not mean 
the program change the fact that the program halts or not.

Basically the halting problem deals with the structural aspect of 
the program itself and not the inputs on it. (this does not mean 
that the input is not required)

Here is the only example that comes to mind.

main(S) { for(;;) if (S subset of S) halt; }


Ok? easy program right. Just checks if S is a subset of itself 
and halts, else doesn't.

But what happens when we call it with the set of all sets?

Such a program is indeterminate. Why? Because the set of all sets 
that do not contain themselves both contains itself and doesn't 
contain itself.  (the if statement can't be computed)

i.e., Let S = Set of all sets that do not contain themselves.

If S doesn't contain itself in, by definition, S is a subset of 
itself... which is contradictory.

If S contains itself, then again, by definition, S is a set that 
does not contain itself, which is contradictory.


Hence, the program give above's halting state can't be known.. 
or, can't be determined, or is undecidable.

All you have to do is ask yourself if it halts(for the given 
input)? You can't even reason about it. Because if it does halt 
then it doesn't halt.