This may be off topic, but here I go anyway...

Back in the school days, I joked that the Halting Problem is actually easy to solve with a Turing Machine. Since a Turing Machine is a theoretical device that exists only in our imagination, we can just suppose that it is infinitely fast. So, we simply have to load our program in the machine and run it. If the machine doesn't stop immediately, it means that it will run forever.

And what does this have to do with DMD?

Well, I kinda have the same feeling when using it. For my ~10kloc project, I still haven't felt a real need to use a real build system. I just dmd *.d. If any measurable time passes without any error message appearing in the console, I know that my compiled successfully (and it is the linker that is running now).

BTW, 10kloc is not such a large codebase, but this is with DMD 2.063 anyhow, before those improvents ;-)

LMB





On Thu, Jul 25, 2013 at 3:03 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Vote up!
>
> http://www.reddit.com/r/programming/comments/1j1i30/increasing_the_d_compiler_speed_by_over_75/
>
> https://news.ycombinator.com/item?id=6103883
>
>
> Andrei

On Monday, 29 July 2013 at 10:15:31 UTC, JS wrote:
>
> Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s
>
>
> So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total.
>
> Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 ==> 77% longer.

No... it's not. How hard is it to understand that "time" != "speed"? Quote:
"Increasing the D Compiler ***Speed*** by Over 75%"

If you increase your speed by 100%, then you decrease your time by 50%. If you increase your speed by 75%, then you reduce your time by 43%. It's *not* that complicated.

Feel free to reason in whatever unit and or dimension you want, but Walter's affirmations are neither wrong nor misleading.

BTW: According to your "logic", a car that runs 200 mph is a "50% speed improvement" over a car that goes 100 mph. Makes perfect sense.

On Monday, 29 July 2013 at 11:46:05 UTC, Leandro Motta Barros wrote:
> This may be off topic, but here I go anyway...
>
> Back in the school days, I joked that the Halting Problem is actually
> easy to solve with a Turing Machine. Since a Turing Machine is a
> theoretical device that exists only in our imagination, we can just
> suppose that it is infinitely fast. So, we simply have to load our
> program in the machine and run it. If the machine doesn't stop
> immediately, it means that it will run forever.
>
> And what does this have to do with DMD?
>
> Well, I kinda have the same feeling when using it. For my ~10kloc
> project, I still haven't felt a real need to use a real build system.
> I just dmd *.d. If any measurable time passes without any error
> message appearing in the console, I know that my compiled successfully
> (and it is the linker that is running now).
>
> BTW, 10kloc is not such a large codebase, but this is with DMD 2.063
> anyhow, before those improvents ;-)
>
> LMB
>
>
>

The halting problem isn't about something taking an infinite amount of time but about the decidability of it.

For example, we can write a program that will take forever but if it is known to do so and will never halt, then there is nothing special about it.

For example, for(;;); in an infinite loop and will never halt(except when you turn the power off ;) but it's halting state is completely known.

Halting problems are much more complex.

Even something like

for(;;)
{
   if (random() == 3) break;
}

is decidable(it will halt after some time).

I would write a program that is undecidable but the margin is too short! ;)

On Monday, 29 July 2013 at 10:15:31 UTC, JS wrote:
> On Thursday, 25 July 2013 at 21:27:47 UTC, Walter Bright wrote:
>> On 7/25/2013 11:49 AM, Dmitry S wrote:
>>> I am also confused by the numbers. What I see at the end of the article is
>>> "21.56 seconds, and the latest development version does it in 12.19", which is
>>> really a 43% improvement. (Which is really great too.)
>>
>> 21.56/12.19 is 1.77, i.e. a >75% improvement in speed.
>>
>> A reduction in time would be the reciprocal of that.
>
>
> Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s
>
>
> So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total.
>
> Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 ==> 77% longer.
>
> 21.56/12.19 != 12.19/21.56.
>
> The order matters.
>
> To make it obvious. Suppose the running time is 20 seconds. You optimize it, it is 100% **faster**(= 1.0*20 = 20s seconds), then it takes 0 seconds(20 - 20).

That is how you fail a physics class.

s = d/t    =>      t = d/s

100% increase in s = 2*s
let s_new = 2*s

t_new = d / s_new

let d = 1 program  (s is measured in programs / unit time_

therefore: t_new = 1 / s_new  =  1 / (2 * s)  =  0.5 * 1/s
                 = 0.5 * t


Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly.

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.

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"

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.

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?

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.

On 7/29/2013 5:28 AM, John Colvin wrote:
> Seriously... Walter wouldn't have got his mechanical engineering degree if he
> didn't know how to calculate a speed properly.

It's a grade school concept :-)

A college freshman physics problem would be calculating the delta V of a rocket fired in space given the fuel weight, rocket empty weight, thrust, etc.