Could Hypercomputer solve undecidable problems?

348 Views Asked by At

firstly lets assume that a human brain is no more powerfull then a Turing Machine. A question that I would like to ask is whether a hypercomputer capable of doing uncountably many computational steps in finite time with memory to match it could solve undecidable problems that we currently have in mathematics like The Continuum Hypothesis , The Conjugacy problem and others.

I understand that such machine wouldn´t be able to solve its own halting problem, but could solve Halting Problem for any Turing machine. But could it solve the above mentioned undecidable problems?

Furthermore could it be generalised that a hypercomputer capable of doing the same number of computational steps as is the cardinality of set of all Reals could solve problems which are undecidable for Turing Machines(like The Continuum hypothesis) but it wouldn´t been able to solve its own undecidable problems, which would require machine capable of doing the same number of computational steps as is the cardinality of a Power set of set of all Reals, and so on and so on in an infinite hiearchy of levels of undecidability?

Thank you very much for your kind answers, Have a nice day

1

There are 1 best solutions below

3
On

The short answer: yes, broadening our notion of computation can basically make any specific thing become decidable, but we'll never "run out" (and we have to distinguish between algorithmic undecidability and logical undecidability).


"Hypercomputation theory" isn't really a well-defined concept, but rather a catchall term for anything of a computability-theoretic "flavor" which is stronger than classical computability. But let me say a bit about it:

  • The simplest (and historically first) notion of hypercomputation is provided by the concept of oracle Turing machines. The usual undecidable problems - and here we have to contrast algorithmic undecidability (e.g. conjugacy problem) with proof-theoretic undecidability with respect to a fixed axiom system (e.g. the continuum hypothesis with respect to ZFC); it is the former which is relevant here - are usually solvable by a Turing machine with "not too big" an oracle - usually $0'$ or $0''$ suffices. For example, a $0'$-oracle machine can effectively tell whether a given word in a finitely presented group is trivial.

  • An oracle machine, however, is still just a finite-time Turing machine - the oracle merely equips it with "extra information" (and in fact for this reason, I've heard it said that they don't really count as "hypercomputation" notions). A more drastic situation occurs when we look at things like infinite-time Turing machines and their variants. In short, we can indeed cook up (purely theoretical, of course) formalisms describing "computations" with uncountably many steps; while these don't have any bearing on physically realizable systems, they are of interest within mathematical logic (and in particular have connections with descriptive set theory).

  • Now let's talk about CH and other set-theoretic questions. As remarked above, the sense in which CH is undecidable doesn't have anything to do with computations: it's simply a feature of the set of axioms we choose to work with (certainly CH is decidable in ZFC+CH :P). Independence from a set of axioms is not a priori connected with computational considerations (although there is significant overlap between the two). However, we can still try to fold such problems into the framework of hypercomputations. Most simply, we could talk about a general version of the problem. For example, let's think about generalizing CH: given an ordinal $\alpha$, decide whether $2^{\aleph_\alpha}=\aleph_{\alpha+1}$. That is, we've moved from the single statement CH to a general "ordinal decision problem" - and it makes sense to ask whether a given model of "ordinal computability" (e.g. ordinal Turing machines) is guaranteed to be able to solve that problem. Now we often need to phrase such questions carefully - e.g. it's consistent with ZFC that the "CH decision problem" is really simple or that it's extremely complicated - but the idea makes sense and can be quite interesting.

  • Meanwhile, your intuition that there will always be an "endless hierarchy" of stronger and stronger notions of computability is of course correct: the usual consideration of the halting problem, abstracted, shows the limits of any fixed theory of computability.