Can we avoid some uses of Church-Turing Thesis, by building "interpreters"?

122 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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).