0

Clearly, I do not have a solid grasp on a number of the following topics, and I would like to. I’ll try to explain my reasoning clearly, so anyone could point out any of my misunderstandings.

The Church-Turing Thesis

This is commonly understood to be a claim that a Turing machine is a “universal” model of computation: a Turing machine can compute anything that is computable, and anything that is computable requires only a Turing machine to be computed. It means that there is nothing “more powerful” than a Turing machine.

It is not a mathematical theorem, and it is not proven. It is called a “thesis” because it links what is a mathematically-definable object (a Turing machine) with a set of conceptual criteria, which together are known as an “effective method”. An effective method must meet the following descriptions:

  • It consists of a finite number of exact, finite instructions.
  • It always finishes (terminates) after a finite number of steps.
  • It always produces a correct answer.
  • It can be done by a human without any aids.
  • Its instructions need only to be followed rigorously to succeed.

An effective method is a philosophical idea, which could be synonymously described as “a perfect methodology”. If, as a logician, you want to reduce some expression to its simplest form and obtain a value that that expression is equivalent to, there may be situations where the expression someone has written down doesn’t reduce to some value (like a number). You might wonder, “How can I know if a certain mathematical expression can or cannot be calculated to return a result?” The Church-Turing thesis says, any mathematical problem can have an answer, if it is the kind of function a Turing machine can resolve.

Thus, this thesis may sound a bit misleading. It is not saying anything about the mathematical properties of a Turing machine. It is claiming that the answer to a more open-ended philosophical problem (“How can I get an answer to my question?”) is, if it’s computable, you’ll get an answer; if it’s not computable, you won’t.

We have to consider that this idea could have been more striking in a period of intellectual history before it was extremely common to think of the physical universe as a manifestation of computation-like physical laws. At the same time, the Church-Turing thesis is not specifically about the physical world, but about the human mind: if it’s not computable, you can’t know the answer. It seems to be saying, essentially, that the human mind itself, is basically a Turing machine.

Importantly, the Church-Turing thesis isn’t proven, so it’s deeply misleading to call it a “thesis”, because it could give people the impression that it’s some sort of conclusive finding. Actually, it should be called the “Church-Turing hypothesis” - as of yet, completely unresolved.

Is this interpretation wrong or right?

The Physical Church-Turing Thesis

This is a modification of the CT-thesis which says that our physical universe is built on mathematical laws (or functions) that are within the same complexity class as Turing machines. It means that algorithms definable in some set-theoretic universe of a higher complexity class than that of Turing machines can never exist in our physical universe. This is also a hypothesis. There is no reason to assume it as true or false.

But the preceding paragraph needs a lot of elaboration, which is where my mathematics needs work.

The complexity class of an algorithm can be defined as a function dependent on time and memory, representing the set of algorithms a Turing machine can finish computing. Clearly, there is a relationship between ordinal classes in set theory, and complexity classes of algorithms. (See 1.) Perhaps it is as simple as, in a set-theoretic foundations of mathematics, everything (including functions, numbers, etc.) is some set. So, if we wish to compute some function and reduce it to a number, perhaps the complexity class (expressed as a set cardinality) is directly related to the cardinality of some of the sets we see in that function expression. For example, a function making use of an infinite sum might be in complexity class aleph-null?

Hypercomputation

Hypercomputation is both the theoretical and the real-world possibility of an “effective method” (let’s say) that can operate in domains of higher cardinality than that of Turing machines (I think). For example, one could consider a Turing machine under idealized conditions (such as infinite time), but I would hope this would be mathematically equivalent to a different formulation - that of a different model of computation altogether, but while operating under realistic constraints (i.e., finite time and memory, since if hypercomputers could be built, one would hope to actually make use of them).

There are various ways of defining a Turing machine, which are provably identical. A common one is lambda calculus. This is a formal system which is Turing complete. But if we are to work in a fully axiomatic system, it is of deep interest to know what the simplest set-theoretic definition of a Turing machine is. I think this is discussed in this article which I want to read.

Basically, one would like to know where in the cumulative hierarchy of sets (at least in ZFC) we first see a set-theoretic description of something beyond a Turing machine. Maybe this is provably impossible, but I know with different set-theoretic axioms, one can absolutely generate universes of higher cardinalities.

For example, ZFC pre-assumes the existence of an infinite set, in its axioms. This is arguably philosophically shocking, yet, apparently constructs a set-theoretic universe in which we can define mathematical objects which describe our universe well. Without the axiom of infinity, you are in some lower cardinality set theory, I think called “finite ZFC”. There are other axioms that define larger universes (I think they might be “unreachable cardinalities” or “Woodin cardinals” or something).


Is hypercomputation mathematically nonsensical? Is the Church-Turing thesis saying that even if we can invent higher cardinalities in our mathematical designs, we are still fundamentally limited in actually doing concrete work in those cardinalities, because, maybe, they are built in a language that is necessarily Turing-complete?

Or, is hypercomputation (trivially) believed to be physically impossible, just because no one knows of any laws of physics which need to be formulated in a larger set-theoretic universe than ZFC? (Are there any aspects of string theory that could hint at this?)

9
  • 1
    Hypercomputation is a commun idea. It's a privilege actually. Unless there is simply a constant or operator to calculate this universe, this can be hypothetical.
    – fkybrd
    Commented Mar 24 at 22:23
  • 1
    I'm imagining Robot saying, "That does not compute." :-) Computers aren't enough for people? They want... Something more than that?
    – Scott Rowe
    Commented Mar 24 at 22:34
  • 1
    It is highly unlikely that the laws of nature are in any sense computable by a TM. TMs have time/space constraints, so that for example, if you have too many bodies in a multiple-body system, the "computation" should not be able to keep up with it but there is no evidence that this ever happens and no one thinks it will. The multiple bodies will theoretically continue to follow the laws no matter how many there are. Commented Mar 24 at 22:42
  • 1
    @DavidGudeman: Turing machines have no such constraints. The physical computers we use in real life have constraints, but if you account for those constraints strictly, then physical computers are not Turing machines but instead very complicated DFAs. Turing machines are a useful model of physical computers, because for any specific instance of an algorithm that halts, there is a finite amount of time and memory required, so with enough effort, physical computers can be persuaded to solve any specific Turing-computable problem.
    – Kevin
    Commented Mar 24 at 22:46
  • 3
    Hypercomputation is perfectly sensible mathematically, Turing himself proposed a model of it using higher ordinals. The Church-Turing thesis is an empirical generalization that it is not physically realizable, and it is as proven as evolution or relativity theory. It cannot be proven any other way, being empirical. Turing explicitly analyzed various known models of computation and showed that they reduce to TM. New models that emerged since (neural networks, quantum computers) also obey the thesis. So until a physical realization is found, hypercomputation will remain a mathematical toy.
    – Conifold
    Commented Mar 25 at 0:16

1 Answer 1

2

Basically, one would like to know where in the cumulative hierarchy of sets (at least in ZFC) we first see a set-theoretic description of something beyond a Turing machine. Maybe this is provably impossible, but I know with different set-theoretic axioms, one can absolutely generate universes of higher cardinalities.

This is actually quite straightforward to mathematically construct. The simplest way to do so is with what is called an "oracle machine." An oracle machine is an ordinary Turing machine, but equipped with an "oracle" that can, in one step, resolve some problem (which may be uncomputable). For example, you might imagine a halting oracle, that can tell whether any given Turing machine halts (but, crucially, the oracle can't tell whether a given oracle machine halts, so that the halting problem's proof does not apply to it and the construction is logically consistent). An oracle machine equipped with a halting oracle is provably capable of computing things that cannot be computed by a regular Turing machine.

Unfortunately, nobody knows how to build a machine like that. The mathematical construction treats the oracle as a "black box" and provides no insight into how it might work. It is simply defined into existence. The physical Church-Turing thesis, if it is correct, holds that such a machine cannot be built. The traditional Church-Turing thesis, if you agree with it, holds that such a machine does not correctly capture the notion of "effective computation" - and it is difficult to argue with that, because (again) the math doesn't tell us how the machine works or how we ought to simulate it.

Perhaps we are mistaken, and there is some incredibly complex and subtle means of building one of these halting oracles. But people have invented many different models of computation that do have obvious means of realization, and all of those models (so far) have been Turing-equivalent or weaker. The Church-Turing thesis may be thought of as an empirical observation. If somebody demonstrates how to build or simulate an oracle machine tomorrow, then the thesis would probably need to be revised or discarded, but until that happens, it's the best explanation we have.

6
  • 1
    "And then a miracle occurs."
    – Scott Rowe
    Commented Mar 24 at 22:41
  • 1
    Since only the number system used is incremental, OM is equivalent to TM.
    – fkybrd
    Commented Mar 24 at 22:52
  • 1
    @fkybrd: I must admit that I am completely baffled by that comment. What is an "incremental number system," and what does it have to do with my answer?
    – Kevin
    Commented Mar 24 at 22:54
  • 1
    @Kevin OM is a quantum computing. The processing of symbol cells will again be complicated. Just like QM. Only the number of digits used for cardinality increases over time. In addition, hypercomputation would be needed rather than big data to know the prophecy. Since there is continuity, dynamism is inevitable. Like the time machine, OM is still an unobtained, sci-fi machine. But the idea is good.
    – fkybrd
    Commented Mar 24 at 23:19
  • 2
    @fkybrd: To the best of my understanding, a quantum computer can be simulated by a classical computer, albeit very inefficiently. If my understanding is correct, that would put quantum computers firmly on the Turing-equivalent side of the discussion.
    – Kevin
    Commented Mar 24 at 23:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .