20 Nov
2003
20 Nov
'03
8:36 a.m.
From: ard(a)p850ug1.demon.co.uk
Hi
I believe that Turing proved that if it can be calculated
by a computer, it can be computed on a Turning machine. It
is the reverse that may not be true since the computer may
not be flexable enough. Turing didn't make comments as to
how large a Turing machine was to do this, only that it could.
Dwight
In the case of Turing closure, the notion is much broader. Turing closure
refers
to the ability of a system to perform any and all computations that can be
expressed. Now, there are problems with this notion, since Godel has shown
that some expressible computations in fact can not be computed. Still, the
general notion is: all that can be computed is computable upon a TM, and a
TM
is capable of computing all computations.
Care to explain this in a way which is not either self-contradictory
('There are functions that can't be computed, but a Turing machine can
computer all functions) or tautological ('A Turing machine can compute
all functions that can be computed on a Turing machine')?
-tony