Hypercalcul

The term hypercalcul indicates the various methods suggested for calculation of function not turing-calculable. It was initially intoduit by Jack Copeland. One also employs the term of calculation super-Turing , although that of hypercalcul can be connoted tempting possibility that such a machine is physically realizable. Certain models were proposed, like networks of neurons with real numbers as weight, a capacity to lead an infinity of calculations simultaneously or the aptitude to carry out nonTuring-calculable operations, such as limits or integrations.

History

A model more powerful than the machines of Turing was introduced by Alan Turing into its article Systems off logic based one ordinals in 1939. This paper examined mathematical sytèmes in which one has a oracle able to calculate a single arbitrary function (not-recursive) of the natural towards the natural ones. It used this machine to prove that even in these more powerful systems, the indecidability is present. This text of Turing highlighted the fact that the machines oracles were only mathematical abstractions, and could not be physically realized.

The challenge of the hypercalcul

Today, the algorithmic Théorie of information makes it possible to better include/understand what the hypercalcul requires. The trademark of a hypercalculator is his capacity to solve the Problème of the stop, that whose ordinary computer is unable. However, a normal computer can calculate the Prédicat of the stop of any program being given the probability of stop

\ Omega

, which is a real number Aléatoire - and contains a infinite information consequently.

\ Omega

is thus an oracle for the program of the stop. The representation of this quantity requires an infinite number of bits on some medium that it is (it is incompressible essentially), and there does not exist any procedure of decision to calculate it. However, a hypercalcultor should obtain

\ Omega

by other means that Turing-complete calculation.

There exists a procedure of approximation for the discrete calculators (ordinary computers) which makes it possible to approximate $\ Omega$ using a simple programme of time-sharing. It is not on the other hand possible to know at which point this program is close d' $\ Omega$ at a given moment.

Theoretical and conceptual possibilities hypercalculateurs

a discrete computer having access to the probability of stop $\ Omega$ can solve the problem of the stop. For a program of $n$ bits in entry, the reading of the $n$ first bits d' $\ Omega$ gives the number of programs $k$ which finish among the $2^n$ programs. One proceeds then as follows: with each stage $i$ , one carries out the $i$ first instructions of each $2^n$ programs. One thus increments $i$ until $k$ programs finished. It is enough to check that the program in entry in fact part.
a machine of Turing able to carry out an infinity of stages. (see Supertâche)
a real computer (a kind of analog Computer ideal) could carry out hypercalculs if physics admitted real variables in the broad sense (and not only of the calculable real numbers), and if one found a means “of domesticating them” for calculation. That would call enough upon physical laws diverting (for example, a Constante measurable physics with an oracular value, like the constant of Chaitin), and would require to be able to measure a real physical value with an arbitrary precision in spite of the thermal Bruit and the quantum effects.
a mechanical system quantum which uses (for example) an infinite superposition of states to calculate a calculable function not . Such a system could not be a quantum Calculateur ordinary, because it was proven that the quantum computers are turing-reducible (they could accelerate the programs solving certain problems but would not allow to solve new problems).
a digital computer being in some Space time, called Space time of Malament-Hogarth, could achieve an infinity of operations while remaining in the Cone of light of a certain space-time event.

See too

Thesis of Church-Turing
Oracle (machine of Turing)

Random links: