Jaa

Establishing the existence of uncountable number of Accelerated Turing Machines

  • Artikkeli

Abstract. We examine the converse of Church-Turing thesis and establish the existence of uncountable number of Accelerated Turing machines, which leads to the conclusion that these machines are unaffected by Gödel's incompleteness theorem.

The Converse of Church-Turing Thesis

 In general terms, the Church-Turing thesis asserts that every effectively calculable function is computable by Turing machine. A function is said to be effectively calculable if there exists an effective or mechanical method for calculating the values of the function. In this regard, a method, or procedure, M, for achieving some desired result is termed 'effective' or 'mechanical' if

(1)  M is set out in terms of a finite number of exact instructions, where each instruction is expressed by means of a finite number of symbols;

(2)  M will, if carried out without error, produce the desired result in a finite number of steps

(3)  M can, in practice or in principle, be carried out by a human being unaided by any machinery save paper and pencil;

(4)  M demands no insight or ingenuity on the part of the human being carrying it out except that which is needed to understand and execute the instructions.

In essence, an effective procedure is a procedure that can be carried out in finite means by a human mathematician, any human mathematician, without requiring any intelligence or insight. For such a procedure, assuming an appropriate book keeping facility, if one mathematician pauses the computation at any point, then any other mathematician should be able to resume the computation from that point and complete it without any difficulty, no matter how much these two mathematicians differ in their intelligence and experience. That is, an effective procedure never relies upon a particular ability of one particular mathematician. Instead, it relies upon something that all mathematicians are expected to have in common – the ability to compute. In this respect, a procedure that can be carried out only by a particular mathematician or by some special group of mathematicians cannot be termed effective.

The notion of effective procedure essentially aims at minimizing epistemic dependencies in the procedural descriptions [7]. Does this mean the procedure would get closer to ontic reality? We do not believe it to be so for at least two reasons:

  1. The ontological truth may not always be the same as what all epistemic facts claim it to be. There exists no known way of comparing ontological truth with epistemic facts other than through observation. This is apparent from the results provided by Turing that there can exist a universal machine that can mimic the behavior of all Turing machines but there cannot exist any universal machine that can predict the behavior of all Turing machines correctly [4, 5].
  2. Accounting for being compliant with all epistemic views may render the procedure move further away from ontic reality. It is seldom true that two radically different epistemic views can agree upon the same fact, and when they do it is always possible that they both miss some fundamental point hitherto unknown. Views of classical and quantum mechanics are good example for this.

Of particular interest for us in this regard would be the converse of Church-Turing thesis that raises the question, can Turing machines compute only effective procedures? Stated in Copeland [1] terms, we have the question,

Are there mechanical procedures that are not mechanical?

While this might seem a paradox at first, given our above explanation of what constitutes a mechanical procedure and effective calculability, it nonetheless is a valid question in that its answer could provide means for the success of artificial intelligence. The issues that need to be explored in this regard are,

  • What class of abilities can be regarded as being attributable to individual mathematicians that can cross the barrier of effective computability while still holding the view of being a mechanical procedure? (Needless to say that intelligence and experience will be the obvious first candidates to go into that class.)
  • How does a mechanical procedure use such an ability? What would be the requirements and restrictions for such specification?
  • Given one such non-effective mechanical procedure, would it always be possible to come up with an equivalent effective procedure and vice versa?

It is worth noting that the notion of effective procedure does not speak about the efficiency of the human mathematician. Thus we are free to choose between a lazy mathematician who would take one minute rest after each step, and a hard working mathematician who could increase his speed with every step. The effectiveness of the procedure guarantees that both would eventually solve the problem in the same way, i.e. either both would halt with same results or both would not halt.

In fact, this concept of increasing the speed with every step forms the basis for one of the hyper machines known as accelerated Turing machine that can arguably solve even the Halting problem [3, 2]. Typically a hyper machine is a machine that could compute functions that are beyond the power of Turing machines. An accelerated Turing machine works by doubling its speed with every step, performing its first step in one unit time and each subsequent step in half the time of the step before. Since 1 + ½ + ¼ + … < 2, such a process could complete infinity of steps in two time units. The important point to be noted here is that no function requires more than 2 time units to be computed on these accelerated machines. In fact, we can slightly modify these temporal sequences and get some machine that would take 3 time units or 4 time units or in general n time units (it is the constant-time guarantee that is more important and not the actual "acceleration" value).

The advantage with this scheme of modifying the temporal sequences is that we can establish the existence of uncountable number of accelerated Turing machines.

For example, let T < a1, a2 …> denote an accelerated Turing machine T with time sequence
a1, a2…

For traditional machines, as described by [3, 2], these values would be

a1=1, a2=1/2, a3=1/4…

Suppose we alter this sequence slightly by making

a2=1/2-0.01 and a3=1/4+0.01 to produce a new sequence

a1=1, a2=1/2-0.01, a3=1/4+0.01, a4=1/8, a5=1/16…

that would result in a new machine T' that is different from T but requires no more than 2 time units (we do not go into the practicality issues here). 

Now, let the set of all possible accelerated Turing machines be given by,

A = {T< a1, a2…> | (lim n->∞ ∑i=1->n ai)  =C, C∈N}.

 Theorem1. The set A is uncountable.

 Proof:  Each element of A is a convergent series of non-negative rational numbers. Each series
a1, a2… converges from some real number r ∈ R to some constant integer C ∈ N.

 We can express this convergence condition as a function f: R→N.

Thus we have, A = {T < f > | f: R→N}.

Clearly A is as big as the set of total functions from real numbers to natural numbers.

Let S = {g | g: N→N} be a set of total functions on natural numbers.

Since N⊂R, it holds that ||S|| ≤ ||A||.

However, the set S is uncountable; thereby the set A also should be uncountable.

An important consequence of this above theorem is that there are more accelerated Turing machines than there are natural numbers. This is in contrast to conventional Turing machines, of which there are exactly as many as there are natural numbers. Because there are uncountable many different machines, it is not possible to have a system of finite description that is capable of describing them all. There is therefore no Gödel sentence for the accelerated Turing machines. Thus there would be no self-referencing and halting problem for these machines [6].

 References

[1] Jack Copeland . The broad conception of computation . American Behavioral Scientist, 40:690–716, 1997.

[2] Jack Copeland. Unconventional Models of Computation, chapter Even Turing Machines Can Compute Uncomputable Functions, pages 150–164. Springer-Verlag, 1998.

[3] Toby Ord. Hypercomputation: Computing more than the turing machine . Technical report, University of Melbourne, Melbourne, Australia, September 2002.

[4] Alan M Turing. On computable numbers, with an application to the entscheidungs problem. Proc. Lond. Math. Soc., 43(2), 1936.

[5] Alan M Turing. Systems of logic based on the ordinals. Proceedings of the London Mathematical Society, 45:161–228, 1939.

[6] Lucian Wischik. A formalisation of non-finite computation. M.phil dissertation, Cambridge, 1997.

[7] Atmanspacher, Harald, 2001, Determinism is Ontic, Determinability is Epistemic, PhilSci Archive.

Comments

  • Anonymous
    October 16, 2008
    excellent article....the examples are very lucid and its great... much more mathematical logic...easily explained.. thanks.. Sergey Google corp.

  • Anonymous
    April 23, 2009
    Well explained.. font is too small

  • Anonymous
    June 13, 2009
    話題の小向美奈子ストリップを隠し撮り！入念なボディチェックをすり抜けて超小型カメラで撮影した神動画がアップ中！期間限定配信の衝撃的映像を見逃すな