On Thu, Jun 19, 2014 at 08:31:53PM +0000, via Digitalmars-d wrote: > On Thursday, 19 June 2014 at 19:37:32 UTC, H. S. Teoh via Digitalmars-d > wrote: > >But the non-solvability of the halting problem means that there is no > >algorithm that can compress every possible program. > > Even if true, programmers don't write every possible program when they > try to write @safe code.
So how do you, as a compiler writer, predict exactly which programs your users will write? -- because without knowing that, you cannot know which analysis algorithms to implement that will solve the N-step halting problem for all the programs that users will write (even though that's only a very small finite set out of the space of all possible programs!). So the only remaining approach is to consider all possible programs. Which means you have to implement exhaustive state space search. Which is impractical for the reasons I stated. T -- This is a tpyo.
