[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.