0
$\begingroup$

I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling a Turing Machine with this language. Like Turing Machine has completeness, the fact to simulate it shows the language has completeness too.

So, to prepare this, I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine. If I do a similar program in my computer language, is that enough to prove the completeness of this latter?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine

This is not enough. You still need to prove, that your class can simulate ANY Turing machine.

Normally to show Turing completness one will

  1. Implement Universal Turing Machine in this language and

  2. Show how unlimited tape is possible.

Of course unlimited tape is impossible in realistic hardware, but even for idealized translation model for languages like C, there are problems

Also I want to add one more clause: make sure that your language well-defined enough. It shall either have mathematical definition or clear formal translation model in language standard.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for your answer! So, concretely it's just that my class must take as parameter the 7-tuple defining the Turing Machine? I can see pretty much what is a Universal Turing Machine (a Turing Machine that can simulate all Turing Machine), but I'm having a little trouble seeing how to implement this $\endgroup$
    – Oromis
    Commented Jul 1, 2019 at 23:36
  • $\begingroup$ @Oromis, look at rosetta code for sample implementations in dozens of languages: rosettacode.org/wiki/Universal_Turing_machine $\endgroup$
    – Konstantin Vladimirov
    Commented Jul 2, 2019 at 6:06
  • $\begingroup$ The only difference I see, it's just that the constructor take all the parameters defining the Turing Machine that the UTM must simulate $\endgroup$
    – Oromis
    Commented Jul 2, 2019 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.