# Is the language $\{a^nb^{2^n}|n\geq 0\}$ Turing recognizable/decidable?

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

• "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. – Raphael Jan 29 '17 at 22:27