0
$\begingroup$

The Church-Turing thesis states that the computation ability of Turing machine is stronger or equal to any "computability model" (whatever that means) we can come up with. Are we able to find some property, satisfied by Turing machine, and any other "computability model" satisfying the property, is Turing complete?

In summary, what I'm hoping for is:

  1. Some suitable definition of a computability model (which should include Turing machine);
  2. A property of computability models;
  3. A proof that Turing machine satisfies this property;
  4. A proof that any computability model satisfying this property is Turing complete.

A possible answer could be partial combinatory algebra. It seems that any pas that is combinatory complete can (roughly) express the untyped $\lambda$-calculus, thus Turing complete, but I'm not very sure.

$\endgroup$
4
  • $\begingroup$ Have you read what Turing (and Church) actually wrote about this? To be clear, I haven't, but presumably they say something to clarify what they mean by "computability model". $\endgroup$
    – Arthur
    Feb 26, 2022 at 7:11
  • $\begingroup$ The Church-Turing thesis is a philosophical conjecture. It cannot really be proved or refuted, except maybe refuted by a new philosophy idea. I’d go to a philosophy forum instead of a maths one. $\endgroup$ Feb 26, 2022 at 11:04
  • $\begingroup$ Turing completeness would be one example of such a property... $\endgroup$ Feb 26, 2022 at 11:46
  • $\begingroup$ Although it doesn't do exactly what you wanted, Section 6.5 ("Church's Thesis") of Joseph Shoenfield's book "Mathematical Logic" may be useful for you. (I certainly was for me.) $\endgroup$ Feb 27, 2022 at 0:40

1 Answer 1

1
$\begingroup$

If you read Turing's paper, you'll find that Turing tried to figure out a way to capture any kind of computation ... and this is what led him to the notion of what we now call the Turing-machine. And if you read his paper and reflect on it, you'll find that it is indeed quite plausible that any computation would be reducable to Turing-computation. But can we prove it? No. You would be trying to prove that this mathematical definition of a Turing-machine does capture out intuitive concept of computation ... and that is just not mathematically provable.

It's like Cantor's notion of cardinality. We can't prove that cardinality is the correct way to think about the 'sizes' of infinite sets and how to compare their relative sizes ... but it sure turns out to be a very useful definition.

$\endgroup$

You must log in to answer this question.

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