2
$\begingroup$

It is known that reachability of 2-counter machines is undecidable. As far as I know, it is semi-decidable though.

Now let's focus instead on the problem of deciding if a 2-counter machine has a computation which passes through the initial state infinitely often.

My understanding is that this problem is non-RE. Is this correct? If so, is there any reference in the literature?

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.