Stathis,
>
> From the SEP article:
> that a human being unaided by machinery is capable of carrying out --
> carries no implication concerning the extent of the procedures that
> machines are capable of carrying out, even machines acting in
> accordance with 'explicitly stated rules'. For among a machine's
> repertoire of atomic operations there may be those that no human being
> unaided by machinery can perform."
>
> Is this just being pedantic in trying to stick to what the great man
> actually said? What is an example of a possible operation a machine
> could perform that a human, digital computer or Turing machine would
> be unable to perform?
the idea is simply that the Physical Church Turing Thesis (PCT, or
Thesis M in the article) is distinct from the Church Turing Thesis (CT).
PCT is much stronger than CT; CT is the thesis that UTMs can compute all
functions which are effective, that is, which a human being unaided by
machinery (except paper and pencil) can perform. It is a thesis on the
interface between "intuitive" (not Brouwer's sense) mathematics and
formal logic/computability theory.
PCT is the thesis that those are also the limits of machine operations
in this universe - and is as such an empirical thesis.
I agree with Bruno that all empirical evidence in this universe suggest
that CT = PCT. But this need not be so, in a logical sense.
There could be physical machines exploiting local infinities which were
strictly more powerful than effective methods/CT/human beings.
See for instance this paper:
Copeland, B. J. & Shagrir, O.
Physical Computation: How General are Gandy's Principles for Mechanisms?
Minds and Machines., 2007, 17, 217-231
Abstract: What are the limits of physical computation? In his `Church's
Thesis and Principles for Mechanisms', Turing's student Robin Gandy
proved that any machine satisfying four idealised physical `principles'
is equivalent to some Turing machine. Gandy's four principles in effect
define a class of computing machines (`Gandy machines'). Our question
is: What is the relationship of this class to the class of all (ideal)
physical computing machines? Gandy himself suggests that the
relationship is identity. We do not share this view. We will point to
interesting examples of (ideal) physical machines that fall outside the
class of Gandy machines and compute functions that are not
Turing-machine computable.
See also:
http://en.wikipedia.org/wiki/Hypercomputation
Read especially (at the end): "As long as there is no physically
plausible way to build such a device, hypercomputers will exist only as
mathematical models."
I don't think that current science suggests in any way that such
machines are possible. But nevertheless we shouldn't ignore the
possibility.
Cheers,
Günther
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Sat Dec 27 2008 - 14:53:47 PST