20 Nov
2003
20 Nov
'03
11: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
20 Nov
20 Nov
12:15 p.m.
Dwight K. Elvey wrote:
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
But most of the time Computer Science deals in abstact rather than
"How %^$#! do I get my scroll wheel disabled in the game I am playing"
as practical problems. ( I am playing a RPG and the scroll wheel
selects spells used by the middle and left mouse buttons. Since the
mouse has the scroll wheel and the middle mouse button combined this
leads to problems if you hit the scroll wheel by mistake. )
Scotch tape or hot glue may be the answer.
Ben.
5:55 p.m.
From:
ard(a)p850ug1.demon.co.uk
>
> 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
11:39 p.m.
No, Turing showed that if it can be computed, it is
computable on a
TM.
Not quite, unless you define "can be computed" in terms of Turing
machines or something provably equivalent to Turing machines, in which
case it becomes a tautology.
What Turing showed is that certain other, intuitively plausible, models
of (discrete) computation are all equivalent to Turing machines in
terms of what they can compute. He did not show that there are no
other possible models of computation, not even of discrete computation;
indeed, without a precise definition of what "computation" means,
nobody can. (As I remarked in this connection in a different message,
there are operations describable in the language of analysis and
calculus that no discrete device, including a Turing machine, can ever
carry out, so I suspect it is already false. However, I also suspect
this is not often realized, because our notion of what constitutes
computation is so bound up with discrete devices.)
There is no machine existing, no machine which may
exist, that can
compute a computation which is not also computable on a TM.
This statement amounts to stating that nobody will ever develop a
notion of computability that includes things TMs cannot compute. While
this may be true, it is a prediction, not a statement of current fact.
(As I noted above, I suspect it is a statement of current non-fact.)
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse(a)rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B
21 Nov
21 Nov
12:09 a.m.
No, Turing showed that if it can be computed, it is
computable
on a TM. There is no machine existing, no machine which may
exist, that can compute a computation which is not also
computable on a TM.
Close - but to be precise you need the word "deterministic" in there
somewhere (which is where quantum computers show specific promise).
Essentially, the set of "computable functions" (I forget the precise
technical term); the set of results that can by computed by a Universal
Turing Machine; and the set of results that can be computed by a computing
system that meets a remarkably small set of requirements are all identical
(given infinite time and memory :-)
"If it is powerful enough to be useful, it is powerful enough to write a
self-reproducing program" - I think, but am not sure that I can prove, that
this translates to "if it is powerful enough to be useful then it can have a
virus"
Andy
7:10 a.m.
"If it is powerful enough to be useful, it is
powerful enough to write a
self-reproducing program" - I think, but am not sure that I can prove, that
this translates to "if it is powerful enough to be useful then it can have a
virus"
so, . . .
should "virus capable" be the definitive definition of "computer"?
2:44 p.m.
On Friday, November 21, 2003, at 12:10 PM, Fred Cisin wrote:
Isn't an import part of viral activity the ability for the virus to
transmit itself
"If it is
powerful enough to be useful, it is powerful enough to
write a
self-reproducing program" - I think, but am not sure that I can
prove, that
this translates to "if it is powerful enough to be useful then it can
have a
virus"
so, . . .
should "virus capable" be the definitive definition of "computer"?
from a host to a new victim? The hp 41C is a very poor
platform for
viri, becuase
usually for a a file to get in the 41C it usually must be keyed in by
the owner
(who might notice the "payload" as he is entering it)
22 Nov
22 Nov
9:34 a.m.
A non-text attachment was scrubbed...
Name: not available
Type: text
Size: 804 bytes
Desc: not available
Url :
http://www.classiccmp.org/pipermail/cctalk/attachments/20031122/03a34e68/at…
21 Nov
21 Nov
7:29 a.m.
New subject: Computability, Turing Machines (was RE: How many of you like HP41C calculators?)
William R. Buckley wrote:
Turing showed that if it can be computed, it is
computable
on a TM. There is no machine existing, no machine which may
exist, that can compute a computation which is not also
computable on a TM.
I probably was supposed to have learned in my classes, but apparently
have forgotten: what is the definition of "a computation". I'm hoping
that there is a better (more formal) definition than "that which can be
computed on a Turing Machine". Otherwise, the proof that everything that
is computable is computable on a Turing machine is trivial.
9:56 a.m.
New subject: Computability, Turing Machines (was RE: How many of you like HP41C calculators?)
I probably was supposed to have learned in my classes,
but apparently
have forgotten: what is the definition of "a computation". I'm hoping
that there is a better (more formal) definition than "that which can be
computed on a Turing Machine".
I refer the honourable gentleman to
http://en.wikipedia.org/wiki/Primitive_recursive_function
(or the equivalent pages on mathworld.wolfram.com
Andy
7547
days inactive
7549
days old
10 comments
10 participants
participants (10)
-
andyh＠andyh-rayleigh.freeserve.co.uk -
ard＠p850ug1.demon.co.uk -
bfranchuk＠jetnet.ab.ca -
cisin＠xenosoft.com -
dwight.elvey＠amd.com -
eric＠brouhaha.com -
jwest＠classiccmp.org -
mouse＠Rodents.Montreal.QC.CA -
rhudson＠cnonline.net -
wrb＠wrbuckley.com