Quantum computers and computable functions

A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate?

If a function is not computable? Does this mean it will never be computable? Even if we change the axioms which our mathematical system is based on or we find a contradiction in it? Are we never be able to find something in the universe which can calculate these functions?

Is that right?

migrated from cstheory.stackexchange.comJan 17 '15 at 2:05

This question came from our site for theoretical computer scientists and researchers in related fields.

You are correct, a quantum computer defined properly: with a finite gate set and rational (you can relax this to algorithmic, but that can be bit circular) transition probabilities will get you only the computable (by a classical Turing machine) functions. Although it might compute them faster than a classical computer.

To get a hyper-computer (something that computes functions that are not computable by a classical Turing machine), you need to sneak something that usually feels 'non-finitary' into the model -- the most common suspect is a non-computable real number -- which your model then extracts its power from. You can make these sort of models of computation from modifying classical or quantum systems. If I recall correctly, the first definitions of quantum TMs were actually accidentally hyper-computing because they allowed non-algorithmic phases in their operators.

To turn to your last question of "Does this mean it will never be computable?", what you are asking about is the Church-Turing thesis. It states, in its vaguest form, that anything that is computable is computable by a Turing Machine. Most people believe this thesis.

Even if we change the axioms which our mathematical system is based on or we find a contradiction in it?

Here you are asking about Kleene's variant of the Church-Turing thesis. Since the CT-thesis cannot be 'proven' (we can always continue to disagree about the first 'computable' in the vague definition), we have to rely on mathematician's beliefs and philosophical discussion. Most mathematicians believe that in any reasonable axiomatic system, any 'finite-feeling' model of computation will be at most Turing-complete.

Are we never be able to find something in the universe which can calculate these functions?

It is important to note that here you are asking a completely different (but related) question than the previos. You are asking about the physicalist variant of the Church-Turing thesis. Although historically this was not the preferred interpretation of the CT-thesis, from my experience it is now the most common way of reading the thesis. Again, here most computer scientists and physicists familiar with CS believe that all functions computable by machines in the physical world are Turing-computable.

I can make some remarks that might help what you are trying to discuss.

There have already been some mathematically well-defined computational models that can "compute" (define/recognize/etc.) uncomputable languages. For example, there are uncountable many languages defined by probabilistic finite automata with unbounded error [Rabin, 1963]. (The cardinality of computable languages/functions is countable.) A similar result was recently obtained for unary languages defined by 2-state quantum finite automata [Shur and Yakaryilmaz, 2014].

In the above examples, there is no bound on the error. In the case of bounded-error language recognition, it was shown that bounded-error polynomial-time "algorithms" can compute some uncountable languages (functions) [Adleman et. al., 1997] if we allow to use uncountable transitions. (I do not know how we can prove that there is no such transitions in nature.) Moreover, the same result can also be obtain for probabilistic "algorithms" [see this cstheory question]. Recently, it was also shown that polynomial-time constant-space quantum Turing machines (two-way quantum finite automata) can recognize some uncountable languages [Say and Yakaryilmaz, 2014]. In the same paper, also a proof system was given which can verify the memberships of any language with bounded error.

I believe that there are some other computational models or computational set-up's (etc.) that can do beyond deterministic Turing machines.

• But computing uncomputable languages is this not a contradiction that all functions which can be computed are Turing-computable – user3613886 Jan 17 '15 at 12:06
• Let's say 'define uncomputable languages'. Remark that the cardinality of probabilistic Turing machines whose probabilistic choices can be arbitrary real number between 0 and 1 is uncountable. On the other hand, as Artem pointed, the cardinality of any 'finite-feeling' models of computation is expected to be countable. – Abuzer Yakaryilmaz Jan 17 '15 at 13:41