[FOM] Potgieter on hypercomputation

[Vladimir Sazonov]

Apostolos Syropoulos wrote:
In addition, he also notes that "a radical revision in our view
> of space and time might in the future necessity a radical revision of our
> ideas about mechanical computability". I believe we should not wait for
> such a revolution. Instead, we can state that we do not know what are the
> limits of computation and encourage people to work on alternative models
> of computation. To get stuck with the idea that the Turing machine is the
> end of story is pure mysticism.

I will say nothing about hypercomputations. But, as I understand,
some real world limits of computation might lead to reconsidering
(splitting?) the Church-Turing Thesis.

It seems reasonable to assert that our Real World is closed at most
under addition (if closed at all - this is an idealization), but not
under multiplication. The latter leads very easily to physically
not existent exponential computations (2*2*2*...*2 = 2^1000 =
practical infinity). This leads to the conclusion that multiplication
and exponential are only partial functions, although computable.

Even with multiplication as a total function (I actually mean here
a version of Bounded "Arithmetic" of finite binary strings), but
without provably total exponential, there is some subtlety to
define (in fact, to prove correctness of) the universal Turing Machine.
We should consider so called "initialized" Turing Machines with some
"built in" information already written, say in an additional tape.
The proper input should be written separately. Complexity considerations
show that encoding the "built in" information into TM commands is not
efficient enough to prove equivalence with the ordinary concept of TM.
Thus, this seems slightly more powerful concept of computability than
the ordinary TM. Also only for "initialized" TM the existence (in fact,
correctness!) of the universal TM in such "non-exponential World" can
be proved. Thus, the "initialized" version of TM seems necessary and
is really appropriate version having (provably) universal TM.

[
See related formal definitions of H(e,n), M(e,n), e*x on P.98, of {e},
etc. on P. 101, and Propositions on P.102 with comments at the bottom
in

V.Sazonov, An equivalence between polynomial constructivity of Markov's
principle and the equality P=NP, Siberian Advances in Mathematics,
1991,  v.1, N4, pp. 92-121 (English translation of a paper in Russian 
published in Matematicheskaja logika i algoritmicheskie problemy,
Trudy Instituta matematiki SO AN SSSR, 12, Novosibirsk, ``Nauka'',
Sibirskoe otdelenie, 1989, pp. 138--165.)
]

Note that "multiplicativity" of the "World" considered actually plays
an essential role in the proof on universal TM. (But exponential is
unnecessary.)

The above considerations show that "multiplicative/non-multiplicative"
is a borderline. In the case of the "Real World" without (provably
total) multiplication, I see no direct way to demonstrate (like in
the case of "multiplicative World") the existence of universal TM or
any other universal computable function under other model of
computability. There is seemingly also no hope to demonstrate that
any notion of computability in such a "World" is reducible to some
fixed (most powerful in this "World") notion of computability
(a version of TM or any other). Therefore it seems plausible that
the intuitive concept "computable" will actually split into various
formal versions, none of them being the "best" or "most powerful".
Probably many Church-like Theses should hold for various versions
of computability in such an "additive, but not multiplicative World":

CT_i: Such and such informal concept_i of computability is described
adequately by such and such formal model_i of computability so that
all the other formalizations of this intuition_i are reducible
to this one.

I see not so much of fantasy here. Just a program for research related
with complexity theory and weak formal systems (weaker than BA),
probably with some radical reconsideration of the underlying logic.


Vladimir Sazonov