Your error is you are conflating two different mathematical issues.
This
first issue is whether there is such a thing as a universal algorithm. The
answer is yes. The first know examples are the universal Turing machines. Other
universal algorithms were published in the literature as I indicate in the
article.
The other issue lies in this statement from Martin Davis you are
quoting:
This assertion is sometimes heard in the strengthened
form: anything that can be made completely precise can be programmed for an
all-purpose digital computer.
Please note the words "strengthened
form". Martin Davis is moving to a different mathematical question.
The
nuance is in the words "can be made completely precise". The issue is whether it
is possible to tell from a mathematical description of a function whether or not
it is computable. Martin Davis says that for some very precise mathematical
languages the answer to this question is no. This statement applies to a
mathematical language which has the expressive power to state both computable
and non computable functions.
Of course if a function is not computable then
it cannot be computed by a universal algorithm and it cannot be programmed on a
computer. Once the nuance is understood there is no contradiction.
There are
mathematical languages called models of computation which can only express
computable functions. Turing machines is an example. Lambda calculus is another.
When a function is expressed in this language it is computable by definition. In
fact we know exactly from this expression how to compute it. However these
languages have limited expressive power compared to the mathematical language
Martin Davis is analyzing. The non computable functions cannot be expressed in
these languages.
Similarly programming languages can only express computable
functions. They do not have the expressive power to state a non computable
function. Therefore the mere fact that a function can be programmed into a
computer is evidence that it is computable.
This nuance helps understand
this other point.
There is no algorithm that enables one to
decide whether an alleged algorithm for computing the values of a function whose
domain of definition is the set of positive integers, and all of whose values
are positive integers, is indeed such an algorithm. [italics in
original]
Pay attention to the words "alleged algorithm". He
refers to the mathematically precise description of the mathematical function.
He is saying there is no algorithm to determine whether this description
corresponds to a computable function. This is the same point as before
particularized to functions on positive integers.
Your error occurs when you
reach this conclusion:
your computability theory doesn't tell me
how to write the algorithm. You can't even prove that such an algorithm exists,
and once you allege to have such an algorithm, you can't even prove that it is
an algorithm.
Computation theory automatically shows an algorithm
is an algorithm when it is written in a language that can only express
algorithms. Martin Davis' point is specific to the more expressive languages
able to express both computable and non computable functions.[ Reply to This | Parent | # ]
|