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. _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
