# [racket] [Off Topic] Theoretical questions

On Mar 16, 2011, at 8:39 AM, Erich Rast wrote:
>* Good day to everybody,
*>*
*>* I have some fairly theoretical questions not directly related to Racket
*>* but hopefully also not very far off, and since I've been on this list
*>* for many years I thought I might shamelessly tap into its the vast
*>* intellectual resources. :)
*>*
*>* 1.) Is it correct to define computation (theoretically) as the process
*>* of applying the alpha, beta, and eta conversion rules of untyped
*>* lambda-calculus to terms of the calculus, where the input is a term of
*>* the calculus and the output is a term in a normal form, if there is one
*>* and the computation halts?
*>*
*>* I'm a bit worried that the requirement that the output is in some normal
*>* form (if there is one) is perhaps not needed or even too strong.
*
If you are a pure theoretician, this is an acceptable definition.
If you are a programming language researcher, you should use the
approach spelled out in Semantics Engineering with PLT Redex instead.
>* 2.) Is it correct to say that any (finitely) parallel computation can be
*>* expressed in terms of a sequential one?
*>* Seems pretty obvious to me but perhaps I'm overlooking something.
*
No. See Plotkin's paper on full abstraction for PCF. Mid 70s. TCS.
>* 3. ) Is it true that attaching a source of randomness to a Turing
*>* machine from a theoretical perspective turns it into a hypercomputer
*>* (i.e. gives it "super-Turing" capabilities)?
*>*
*>* I believe I've read that somewhere, sometime but unlike the case of
*>* other hypercomputers like the infamous "accelerated Turing machine" it
*>* is not immediately obvious to me why this should be so.
*>*
*>* I'd be glad about answers or good and halfway accessible literature that
*>* deals with these questions. (Perhaps it's better to reply off the list.)
*
I do not know what 'hypercomputer' could mean.