0 votes 0 votes Is this language L accepted by a Turing Machine? L = a1n a2n a3n a4n .........amn || m,n > 0 Also, what about this language? L = a1n a2n a3n a4n .........ann || n > 0 Theory of Computation theory-of-computation turing-machine recursive-and-recursively-enumerable-languages + – Akash Mishra asked Sep 11, 2017 Akash Mishra 1.1k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Rishabh Gupta 2 commented Sep 11, 2017 reply Follow Share I think Yes. Anything that can be done on a digital computer can be done on a Turing machine. But it might be very time consuming and tiresome to program the Turing machine for everything that you program on digital computer. One can try to program the Turing machine for the given language as follows: Start matching each a1, with an a2, then with an a3 , and so on. Then match the second a1, with other a's, and keep doing this. Somewhat similar to $a^{n}b^{n}c^{n}$, but with more variables. 3 votes 3 votes Arjun commented Sep 12, 2017 reply Follow Share Can you write a C (or any language) code to solve a problem? If so then its language is context-sensitive and hence decidable. 3 votes 3 votes Please log in or register to add a comment.
–1 votes –1 votes is first recursively enumerable lang and the second recursive? A_i_$_h answered Sep 12, 2017 A_i_$_h comment Share Follow See all 2 Comments See all 2 2 Comments reply Arjun commented Sep 12, 2017 reply Follow Share why so? 0 votes 0 votes A_i_$_h commented Sep 12, 2017 reply Follow Share nono sorry , it was a mistake 0 votes 0 votes Please log in or register to add a comment.