[Haskell-cafe] Learn You a Haskell for Great Good - a few doubts
alex.solla at gmail.com
Thu Mar 3 23:25:48 CET 2011
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...
More information about the Haskell-Cafe