[racket] [Off Topic] Theoretical questions

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