On 3/18/2011 8:12 AM, Bruno Marchal wrote:
Hi John,
In computer science there is something interesting which can be seen
as a critics or as a vindication of what you are saying. That thing is
the Church thesis, also called Church-Turing thesis, (CT) and which
has been proposed independently by Babbage (I have evidence for that),
Emil Post (the first if we forget Babbage), Kleene, Turing, Markov,
but not by Church (actually).
The thesis has many versions. One version is that ALL computable
functions can be defined in term of lambda expressions, or in term of
Turing machines, or in term of Markov algorithm, or in term of Post
production system, etc. All those versions are provably equivalent.
Such a thesis *seems* to be in opposition with your idea that complete
knowledge is impossible. But it is not.
The contrary happens. Indeed the thesis concerns only completeness
with respect to computability, and then, as I have already explain on
this list, it entails the incompleteness of any effective knowability
concerning just the world of what machines can do.
By "machines" here I assume you mean digital machines/computers. I
think this doesn't apply to machines described by real numbers. But of
course we think it is unlikely that real number machines exist and that
the reals are just a convenient fiction for dealing with arbitrarily
fine divisions of rationals. But there can be a cardinality between the
integers and the reals. I wonder what this implies about computability?
Brent
Church thesis makes it impossible to find *any* complete theory about
the behavior of machines. I explain this in the first footnote of the
Plotinus' paper. I can explain if someone ask more. It is proved by a
typical use of the (Cantor) diagonalization procedure.
It vindicates what you say, really. We can sum up this by
Completeness with respect of computability provably entails a strong
form of incompleteness for our means of knowability and provability
about machines' possible behavior.
This can be proved rigorously in few lines. It is stronger and easier
than Gödel's incompleteness, and it entails Gödel's incompleteness
once we can show that the propositions on the computable function can
be translated into arithmetical propositions (the lengthy tedious part
of Gödel's proof).
Not only Church thesis makes it possible to think about 'everything',
but it makes us able to prove our (machine's) limitation about the
knowledge about that everything. In any case, this makes us modest,
because either CT is wrong and we are incomplete for computability, or
CT is true and we are incomplete about our knowledge about
computability, machines, and numbers.
Best,
Bruno
--
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@googlegroups.com.
To unsubscribe from this group, send email to
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
