[Haskell-cafe] Learn You a Haskell for Great Good - a few doubts

[Alexander Solla]

On Thu, Mar 3, 2011 at 1:58 PM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:

>
> I can't think of an approach that doesn't require all but one of
> the tuple elements to have Bounded types.


It's not possible.  Such an enumeration could potentially have an
uncomputable order-type, possibly equal to the order-type of the rationals.
 (In other words, there could be countably infinitely many elements between
any two elements)

It's possible to define a computational system where you can do arithmetic
on countable ordinals, but it has the expressive power of Turing machines
with oracles (where an oracle is a thing that correctly guesses the "right"
answer for a computation that does not halt in finite time (consider a
sequence approaching pi as a limit).   We can re-interpret the oracle's
guess as passing to a limit ordinal.  In any case, TMs+ oracles are strictly
stronger than just TMs.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110303/6fc83e98/attachment.htm>