1
$\begingroup$

I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L is representing paths on the Cartesian plane which can begin and end at any point so say begin at (1,3) and end back at (1,3). My Question is, you would be able to represent a Turing Machine for this, right? Hence it would be Recursively Enumerable.

$\endgroup$
1
$\begingroup$

Your language is computable, and so in particular recursively enumerable. Given a path on the Cartesian plane, you can decide whether it goes back where it started: just follow the path and see where it ends. You can program a computer to do that. So it is decidable.

$\endgroup$

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.