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

Brent Yorgey byorgey at gmail.com
Tue Sep 4 00:29:54 EDT 2007

On 9/3/07, Vimal <j.vimal at gmail.com> wrote:
> Hi
> In my Paradigms of Programming course, my professor presents this piece of
> code:
> 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:

done = False
while E and not(done) do...

I'll let you work out the rest.  Unless I am missing something here... are
you not allowed to introduce extra variables? It's a strange thing for your
professor to ask, since under reasonable assumptions, anything that is
computable can be done only using if and while.  goto (which is essentially
what break is) is never necessary.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070904/2baa55ee/attachment.htm

More information about the Haskell-Cafe mailing list