[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
>>S
>>if F then
>>break
>>end
>>T
>>end
>>
>>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