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. 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. 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.) Best, Erich -- ---- Erich Rast, IFL Universidade Nova de Lisboa, FCSH Institute for the Philosophy of Language (IFL) Av. de Berna, 26-C 1069-061 Lisboa Tl. (+351) 217993109 _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
