0
$\begingroup$

I have proven that it is not regular and context free. But is it Turing decidable/recognizable? I'm thinking yes, as I am able to write a Java program for it, and by the Church-Turing thesis the power of the Turing Machine and a Java program is equivalent (or am I wrong here?).

$\endgroup$
  • $\begingroup$ "by the Church-Turing thesis the power of the Turing Machine and a Java program" -- you don't need the CT-thesis for that. Prove equivalence by simulation. $\endgroup$ – Raphael Jan 29 '17 at 22:27
1
$\begingroup$

You are right about the fact that being able to conceive a Java program for doing the job, then there must exist a Turing machine which will also recognize that language. However, you don't need the Church-Turing thesis to confirm your statement. You need something weaker, namely the fact that both Java and TM are acceptable programming systems and hence they are isomorphic (ie. they compute the same set of partial functions) by Roger's theorem.

The main point is that Roger's theorem is a theorem and Church-Turing thesis is not proven.

$\endgroup$
  • 4
    $\begingroup$ Well, the Church-Turing thesis isn't provable. It's essentially a definition of computation. $\endgroup$ – David Richerby Mar 31 '17 at 17:38
0
$\begingroup$

Sure, the turing machine would count the a's, than it will calculate 2^n and then count the b's

$\endgroup$
  • 1
    $\begingroup$ The OP already mentioned that they are able to write a Java program for the language. $\endgroup$ – Yuval Filmus Jan 29 '17 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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