I wish to thank Prof. El Naschie for his valuable insights he brought up here, but actually, I meant something else.

Hypercomputation is the computation of functions or numbers that cannot be computed in the sense of Turing, i.e., cannot be computed with paper and pencil in a finite number of steps by a human clerk working effectively. This human computer calculates by rote (reliably but without insight or ingenuity), in accordance with an effective method supplied by an overseer, prior to the calculation. Turing meant by this statement that the Turing-machine-computable functions or numbers include all entities that are calculable effectively — i.e., calculable by the ideal human clerk, described above.

Now suppose that in accordance with correspondence principle we want to establish a mapping H --> S of a Hilbert space H of a system in thermodynamic limit (i.e., the limit for a large number of system’s constituent particles N such as atoms or molecules, where the size of the system is taken to grow in proportion with N) to the system’s configuration space S.

Such a mapping must associate to the eigenspace of the ground energy of the quantum Hamiltonian the set of configurations that is isomorphic to the macroscopic state of the system with the lowest possible energy. However, given infinite number of degrees of freedom existing in thermodynamic limit, there is in general no effective procedure for determining whether or not an arbitrary classical configuration belongs to this set.

At the very least, this implies that the injective computable (with Turing machines) mapping H --> S cannot be defined for the entire Hilbert space of the system, which, in turn, involves as an inevitable result that it is impossible to prove rigorously that classical mechanics is a limiting case of quantum mechanics.

Thus, as it turns out, quantum-classical correspondence is based on hypercomputation, that is, on real-world processes that cannot be simulated by standard (classical or quantum) Turing machines. Or, it only seems that way?

Dear Prof. El Naschie,

You can rest assured that there is no contradiction between what I said earlier and the interpretation you suggest.

Even being agnostic on the subject of the idea of fractal (Cantorian) space-time you advocate, I find quite plausible that the embedded infinity of Cantorian space-time might be a justification for the existence of an infinite time Turing machine.

However, the issue of hypercomputation is not limited (what’s more, it cannot be reduced) to the discussion of the hypercomputational resources that non-Turing machines may use.

Let us consider, for example, a simple problem of elementary Euclidean plane geometry: Given a straight line and a curve decide whether the curve and the straight line intersect within a given square. Despite being a trivial question from a point of view of geometry, the corresponding mathematical problem is algorithmically unsolvable: Given the equations for the straight line and for the curve described by elementary functions with rational coefficients and the number pi, we cannot decide in general whether this curve and this straight line do intersect.

Does this example suggest that perhaps our brain operates with non-recursive processes? If that is the case, hypercomputation is not just the question about unlimited resources.

Claims of hypercomputation are often made a little too easily. 

In the context of the original question, I wonder whether the noncomputability is related to quantum randomness. After all, a true RNG produces a noncomputable function; in a sense it is maximally noncomputable. 

So it isn't the presence of noncomputabilty that is a surprise; quantum mechanics demands it. A perhaps more interesting question is whether a less trivial type of noncomputablity can be achieved that way. I'd venture to answer no. You might want to take a look at a recent paper of mine with Maarten Boudry that addresses a similar question. (It's oriented toward the philosophy of science rather than just physics, but you should at least find some of the references useful.)

Article Beyond Physics? On the Prospects of Finding a Meaningful Oracle

You raised a very interesting subject concerning the relation between randomness and computability.

On the one hand, as follows from simple cardinality arguments, a random real number is uncomputable with probability 1. As Church argued, if a sequence of digits r1, r2, ..., rn,... is random, then there is no function f(n)=rn that is calculable by the universal Turing machine (Church, A., ‘On the Concept of a Random Sequence’, American Mathematical Society Bulletin 46, 1940, pp. 130–135).

On the other hand, can this uncomputability be harnessed in any way? This question was addressed by Shannon et al. as early as in 1956 (see Shannon, C. E., K. De Leeuw, E. F. Moore and N. Shapiro, Computability by probabilistic machines, in Automata Studies, Princeton University Press, 1956). Their conclusions can be summarized in this way: introducing a random element producing equiprobable outputs of 0 and 1 will, indeed, do no better than a deterministic Turing machine.

What’s more important, it is the place where randomness appears in quantum mechanics. As we know, there are two essentially different fundamental processes in quantum mechanics: the unitary deterministic evolution of a wave function in configuration space (governed by the Schrödinger equation with a particular Hamiltonian) and the collapse of the wave function to an eigenstate of the measurement operator. This second process is where randomness enters.

However, as it is showed in the paper  arXiv:1506.00428 uncomputability comes out of the first, deterministic, process and is result of infinite dimensionality of the Hilbert space of the system taken in the thermodynamic limit.

Since the Turing machine is classical, in the sense that the states it uses are classical, the answer, in principle, is affirmative: a Turing machine that uses quantum superpositions of states, i.e. a quantum computer, can represent more complicated calculations than a Turing machine that can only act on classical states, which is a classical computer. These statements, however, don't have anything to do with any intrinsic infinity or impossibility within some mathematical framework, whose assumptions must be carefully studied. The thermodynamic limit of any physical system involves a sequence of finite systems, incidentally, so, once the question of its existence has been settled, the next question is the rate of convergence-and not all sequences converge at the same rate. 

If taken generally it is a good point. But, what I have in mind is quite specific.

Let me start by saying that already in 1964 Komar showed that the behavior of a quantum system having an infinite number of degrees of freedom may be non-computable, proving that, in the most general case, the universal Turing machine cannot determine whether or not two arbitrarily chosen states of such a system are macroscopically distinguishable.

He wrote (see Komar, A., ‘Undecidability of Macroscopically Distinguishable States in Quantum Field Theory’, Phys. Rev., 1964, 133B, pp. 542–544): “Given two arbitrary quantum states of a physical system having an infinite number of degrees of freedom, we know either that they are macroscopically distinguishable, or that they are not. What we have shown is that there is in general no effective procedure for deciding whether they are or not. That is, there exists no effective procedure for determining whether two arbitrarily given physical states can be superposed to show interference effects characteristic of quantum systems.”

Along these lines, in the paper arXiv:1506.00428 it has been demonstrated that the injective computable mapping of the Hilbert space of a certain quantum Ising model in the thermodynamic (i.e., macroscopic) limit to the configuration space of the corresponding classical Ising model in the same limit cannot be defined for the entire Hilbert space.

Particularly, given the eigenspace of the ground energy of the quantum Hamiltonian O and the functor F, there is no algorithm which can in a finite number of steps correctly decide whether or not a given classical configuration S belongs to the set F(O).

Any infinite system is, strictly speaking, ``non-computable'', since any computer can represent finite amounts of data. In this sense, a real number is non-computable. So it's not a particular property of quantum systems at all: any calculation that cannot be  reduced, exactly, to the evaluation of polynomials on the integers is non-computable.  

The  important word here is ``exactly'' and the question is whether there exist physical systems, whose mathematical description can be well approximated by computable functions and how well. This holds, whether the systems are classical or quantum. 

Now, once more, it is known that the space of states of a quantum system is much larger than that of a classical system; as a result, it's a very hard computational problem, starting from scratch, to say something about a state of the quantum system, using classical states. However this doesn't mean that it's not possible to perform *approximate* calculations, with controlled precision, and that's what matters. And what's interesting is that the statements about  a lack of algorithm haven't been compared to known algorithms that do precisely that. 

An important issue is, indeed, how finite representations of the dynamics of physical systems are constructed and what symmetries of the original system do they preserve and how is it possible to describe how the symmetries that are broken in this way are-or are not-recovered in the scaling limit. These are the physically interesting questions and they have been addressed, for quantum mechanics (e.g. http://arxiv.org/abs/math-ph/9805012 )  and quantum field theory. 

The Turing Computer showed first time that it brings new theories and facts into the well known world of Mathematics and Physics. 

A Turing Computer is an object for proofing by his own. The proofed object (real machine or theory) is compared with the Turing Machine.  

That was an historical accident - never before such an artificial product was so important.

The question for exceeding the properties of a Turing Machine is too sophisticated in my way of thinking. It should be change to: Is any new computer or even theory of computing obeying the rules of a Turing Computer? 

This question is very important because scientists are speaking of a Quantum Computer but all reached physical results are far away from a Turing Computer.  

I'd recommend ``Feynman's lectures on computation'', http://www.amazon.com/Feynman-Lectures-On-Computation-Richard/dp/0738202967 for an introduction to these issues.

Dear Stam,

But this is exactly my point: If a quantum system with an infinite number of degrees of freedom is undecidable (i.e., there exists no effective procedure for determining whether two arbitrarily given states of this system can be superposed to show interference effects), then how the correspondence principle (supposedly taking place in the macroscopic limit) can hold true?

Appeal to approximation would not help in this case since here we deal with the principle question of whether or not classical mechanics is a limiting case of quantum mechanics. That is, the point at issue here is the intertheoretic reduction existing between quantum and classical theories. If we put that classical mechanics is only as good as an approximation, then it would mean the intertheoretic elimination of classical mechanics.

As to the lack of algorithms and the comparison between them, it is more relevant for the topic of computational complexity and not to the quandary of undecidability (indeed, only if a problem is decidable, we can ponder what algorithms for its decision can be more or less efficient).

I read your paper “Fast Quantum Maps” (arXiv:math-ph/9805012) attentively. Even though the whole subject of the article is rather far from my field of expertise, I find Finite Quantum Mechanics as a very fascinating object; thank you for bring this paper to my attention.

While the interference effects that arise in quantum mechanical transition amplitudes do, in principle, involve summing over an infinite number of intermediate states, nevertheless, it isn't true that no approximation can be found. The reason is, as is known since Dirac and Feynman, that the intermediate states don't enter with equal weight, but with the exponential of the action, measured in units of hbar-exactly similarly, in fact, as in interference phenomena in classical wave optics. So while the existence of the limit, when taking into account the infinite number of states is useful, its real utility lies in the consequence that it's then possible to use any subset of states, and all don't converge with equal rate.

Classical mechanics *is* an approximation to quantum mechanics and how good an approximation it is can be quantified.

With ``Finite Quantum Mechanics'' it's possible to write down consistent quantum gates, that act on qubits and show how this can be done efficiently.  

Dear Stam,

Unfortunately, such a point of view – that classical mechanics merely approximates quantum mechanics – has been proved wrong long time ago.

Just one example: Suppose that quantum theory is fundamental and universally valid, and the classical world has only “relative” or “perspectival” existence; in other words, classical mechanics is quantum mechanics of macroscopic systems. Then it would imply that the classical motion of macroscopic bodies could be accurately described (with any given accuracy) within standard quantum mechanics.

However, as Zurek and Paz (see Zurek, W.H. & Paz, J.P. ‘Why We Don’t Need Quantum Planetary Dynamics: Decoherence and the Correspondence Principle for Chaotic Systems’, 1995, arXiv:quant-ph/9612037) have estimated, due to its chaotic motion, Saturn’s moon Hyperion (which is about the size of New York) would spread out all over its orbit within 20 years if treated as an quantum-mechanical wave packet (i.e., as an approximation of quantum mechanics).

This means that any classical approximation of quantum laws of motion for such a macroscopic object would break down practically immediately. Obviously, this is a serious problem for the program of deriving classical behavior from quantum mechanics (affecting all interpretations of this theory).

There is a fundamental difference in physical magnitude and space between classical mechanics and quantum mechanics.

I think we shouldn't try to take both sets of objects in one pot.

What we know is that classical mechanics is quite clear to us but quantum mechanics quite a complex set of found (most mathematical) rules. We are very far away of knowing how our particles on quantum level (Fermi-Jones and Bosons) relate to each other and why.  

Every found new mathematical theory in QM is in most cases a supposition.

Dear Franz,

You are absolutely right when you’re talking about the unsettled status of quantum theory.

The relationship between classical and quantum theory is far from being completely understood and thus is of central importance to modern physics. Such problems as the presence of the very special correlations that quantum theory makes possible (forbidden by very general arguments based on realism and local causality), the emergence of a single result in a single realization of an experiment, the presence in parallel of two evolution processes of the same object (the state vector) still loom the same large in our times as they were at the outset of quantum theory.

The very fact that nowadays there are more than nine formulations of nonrelativistic quantum mechanics -- such as the wavefunction, matrix, path integral, phase space, density matrix, second quantization, variational, pilot wave, and Hamilton–Jacobi formulations and also the many-worlds and transactional interpretations -- speaks for itself.

Dear Bernd,

Unlike the art of sound where different tones, apart from cacophony, make music, in a physics science, the diversity of the interpretations (formulations) of a theory means something wrong about this theory.