[Haskell-cafe] [Off topic] Proving an impossibility

Miguel miguelimo38 at yandex.ru
Tue Sep 4 02:10:18 EDT 2007

>On 9/3/07,Vimal<j.vimal at gmail.com> wrote:
>>while E do
>>if F then
>>He then asked us to *prove* that the above programming fragment cannot
>>be implemented just using if and while statement, even if S and T can
>>be duplicated a finite number of times
>But it IS possible.  Just add a boolean flag:

Possibly, you are not allowed to change the sequence of machine operations at all. See, if you change "while(A){B}" to "if(A){B};while(A){B}", the sequence is exactly the same; but it's not possible in this case.
It reminds me of a paper by Knuth, where he states that "goto" statement is necessary; don't remember the title, however.

More information about the Haskell-Cafe mailing list