1
$\begingroup$

Let us be in the case where we want to show that Turing Machines are capable of computing all that System $X$ ($\lambda$-calculus for example) can.

The usual way I see this done, is to describe an algorithm to transform a program in System $X$, to an specific Turing Machine which computes the same. And then invoke Church-Turing Thesis to argue that this algorithm cab be done by a Turing Machine itself.

My question is: What happens if instead of describing an informal algorithm, I write an specific Turing Machine, which has as inputs an specification of a program in System $X$ and another argument, which simulates the procedure that System $X$ would have done with that argument. That is, I write a concrete Universal Turing Machine, but for programs in system $X$. ¿Do I still need Church-Turing thesis?

In some sense. If we replace Turing Machines and System $X$ by let's say Python and Ruby respectively. The first option would be to know that you can translate a program in Ruby to a program in Python. And the second one would be to actually build and interpreter of Ruby, in Python.

$\endgroup$
7
  • 2
    $\begingroup$ Wellllll, yes and no. The church-turing thesis is also used to argue "there's a computer program that does this, but I'm too lazy to write it". Having an interpreter won't solve that usage. Writing a python (say) to turing machine transpiler could be an interesting project, but we already know that python and turing machines have exactly the same computational power, so witnessing that explicitly wouldn't necessarily tell us anything we don't know, or remove any appeals to church-turing. $\endgroup$ Commented Apr 9, 2021 at 17:16
  • 1
    $\begingroup$ The Church-Turing thesis is not a method of mathematical proof. @HallaSurvivor: please name and shame authors who have attempted to use the Church-Turing thesis in the way you describe. $\endgroup$
    – Rob Arthan
    Commented Apr 18, 2021 at 22:48
  • $\begingroup$ @Rob Arthan -- I never said that it's a method of mathematical proof. I said that it's used to justify the existence of a recursive function in the technical sense given only a high level (and informal) description of an algorithm describing a function $\mathbb{N} \to \mathbb{N}$. Surely you cannot accuse Lou van den Dries of misunderstanding the church-turing thesis, but you can see him use it in the sense that I have described throughout his notes here. See, for instance, the beginning of section 5.3. You'll forgive me for not shaming. $\endgroup$ Commented Apr 18, 2021 at 23:15
  • $\begingroup$ @HallaSurvivor I think van den Dries is writing rather confusingly about this. At the only point I can find where he appeals to the Church-Turing thesis in a proof, he "leaves it to the reader to replace this appeal by a proof". An adequate description of an algorithm does not require an appeal to the Church-Turing thesis to show the existence of a Turing machine or a $\lambda$-term or whatever that implements the algorithm. $\endgroup$
    – Rob Arthan
    Commented Apr 18, 2021 at 23:29
  • 1
    $\begingroup$ @RobArthan ¯\_(ツ)_/¯ $\endgroup$ Commented Apr 18, 2021 at 23:30

2 Answers 2

1
$\begingroup$

The Church-Turing thesis is the belief that all effective models of computation are weaker than the Turing Machine.

As it happens, every effective model of Computation that someone comes up with is either obviously implementable on a Turing machine, or has that equivalence worked out.

It isn't hard to show that a Von Neumann machine is more powerful than your desktop computer, and that a Turing Machine is at least as powerful as a Von Neumann machine (both in terms of "what can be computed", speed here is ignored).

And once your program is running on an abstraction of a desktop computer, anything your program does is clearly Turning-computable. There is no need for the Church-Turing thesis here.

The Church-Turing thesis just says "if you invent a new kind of computation, either it isn't physically realizable or you can be pretty certain it is no stronger than a Turing machine".

We have models of computation that are stronger than a Turing machine. The most obvious is a Turing machine augmented with an extra "Halt" instruction. The "Halt" instruction looks at the tape, and if it contains a description of a Turing Machine plus input, it writes 1 if that Turing machine would halt on that input, and 0 if it would not.

This is a model of computation that is stronger than a Turing Machine, but it is also not realizable -- there isn't a Halt oracle.

Quantum computation was sufficiently weird that some suspected it could produce effective computation that a Turing Machine could not model. It turns out the advantage is at best speed not computability.

You could imagine some kind of effective model of computation that is stronger than a Turing Machine. Like, if we found a physical object or phenomena that computes "halt" or something equally powerful.

But, actually writing Ruby to Python interpreters? That isn't needed for a proof. Ruby runs on a system weaker than a Von Neumann machine, which is no stronger than a Turing Machine. So Ruby can be interpreted on a Turing Machine. The same is true of Python. Next, showing that you can simulate a Turing Machine in (an extension of) either language (basically, with memory space issues delt with) and you have shown both are fully Turing-Complete, hence you can know you can interpret one in the other.

And writing an interpreter for a Turing Machine is insanely easier than writing one for Python or Ruby.

$\endgroup$
0
$\begingroup$

You don't actually need to invoke the Church-Turing Thesis in the first place to show that Turing machines are capable of computing everything system X can. Once you've specified how to translate any program in system X to a Turing Machine you've already shown that anything system X can do can also be done with Turing Machines.

You're right to worry about whether this translation process is computable though. Once you have your concrete Universal Turing Machine, you also have a translation process that can obviously be performed by a Turing Machine. Specifically, you can translate a program in system X to your Universal Turing Machine with your program already inputted.

That is, in your Ruby/Python example, say you have a Ruby interpreter in Python whose code is ruby_interpret(ruby_code). Then you also have a Ruby to Python transpiler that takes a program P written in Ruby and outputs the program ruby_interpret(P).

$\endgroup$
1
  • $\begingroup$ I don't understand. In the first paragraph you do not mention that the translation must be computable,and yet in your second pragraph you say it is important. What you describe in your second paragraph is actually my argument, that if I can build this universal machine, then the translation obviously can be performed by a Turing machine. But what if I don't do this, what if I just showed an informal translation? $\endgroup$ Commented Apr 9, 2021 at 17:34

You must log in to answer this question.

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