Re: Turing completeness of the functional paradigm?

Babylonian wrote:
[...]
|The Church-Turing thesis doesn't figure large in my own thinking,
since
|a constructivist cannot identify a class of all constructible
functions
|in the sense of having a proof that f is computable if and only if it
|can be written in a certain language.

This is true in the following sense. One can't
constructively prove that

(*) Any function f from the natural numbers to the
natural numbers is Turing computable.

unless one has already made some additional assumption
beyond what is usual for constructive mathematics. In all
the cases I know of where someone has made an assumption
implying (*), the additional assumption was itself that all
all functions of some class including the total functions
from N to N are Turing computable, which makes proving (*)
somewhat pointless. (The Markov school in Russian is
supposed to have assumed (*) in general. I only know about
them from hearsay and short quotes, though.)

|If he had such a (constructive)
|proof, diagonalization gives him a technique for creating a new
|function outside that class.

No, it doesn't.

The fact that for any sequence of functions f_i : N->N there
exists a g:N->N different from all of them (e.g. g(n)=f_n(n)+1)
is constructive. The fact that for any such sequence of
functions, if they are all computable then so is g is
constructive too.

The statement that the Turing computable functions can be
enumerated in this way isn't constructive. We can enumerate
the Turing machines, m_0,m_1,..., but not the ones that
compute functions N->N. Nonconstructively, one can simply
let i0<i1<i2<... be the indices of the Turing machines that
do compute total functions N->N, by just skipping the ones
that don't. But it's not constructive since there's no method
for determining which do and which don't.

In fact, there's a metamathematical argument showing the
consistency of assuming (*), provided that the remaining
other assumptions are all standard constructive assumptions.
Of course, (*) is inconsistent with classical mathematics
because the simple nonconstructive argument above easily
proves that the existence of a nonrecursive function N->N
follows from the law of excluded middle.

Keith Ramsay

.

Relevant Pages

  • Re: functions that halt
    ... >> there can be no such F that lists ALL the total functions. ... >no programming language can describe all total functions, ... by some algorithm (i.e. you can enumerate its digits). ... >uncountable number of reals in any interval. ...
    (comp.theory)
  • Re: functions that halt
    ... >>no programming language can describe all total functions, ... > by some algorithm (i.e. you can enumerate its digits). ... My proof doesn't concern computability at all, ...
    (comp.theory)
  • Re: CERT C Programming Language Secure Coding Standard
    ... There is an enumerable set of exceptional conditions ... (More likely they meant that it is possible to enumerate all these ... all right to flout the rules if the exceptional circumstances ... The set of all possible Turing machines is ...
    (comp.lang.c)
  • Re: re:Entropy
    ... > We can define a digit sequence without a pattern as one which ... > be generated by a finite Turing machine. ... First you enumerate all the Turing machines using the Godel ...
    (sci.math)
Loading