0
$\begingroup$

word problem: given a language L through a deterministic turing machine, is the word w in the language L?

the problem should be decidable, since if there is a deterministic turing machine i can simply turn that into a dfa take the word w go through the dfa step by step and see if i end in an accepting state?

I now want to know if there is a way to reduce the word problem to sat / cnf-sat or 2-sat. can't think of a way that i could do that so i wanted to ask on here. my professor said i should take a look at the proof for cnf-sat / 3-sat in NP and then see what happens when i translate the word problem for dtm in the same way so i would guess i should check what happens when i search for a way where i try to translate the word problem into a sat/cnfsat/2-sat problem. thanks in advance

Improve this question
$\endgroup$
2
  • $\begingroup$ The answer depends on the language $L$. $\endgroup$
    – Yuval Filmus
    Commented May 14, 2022 at 18:42
  • $\begingroup$ @YuvalFilmus the language L is given through a Deterministic Turingmachine $\endgroup$
    – heythere
    Commented May 14, 2022 at 20:10

1 Answer 1

Reset to default
1
$\begingroup$

The answer is no because the problem seems undecidable.

You can reduce the halting problem to it.

Improve this answer
$\endgroup$
3
  • $\begingroup$ the problem is decidable for languages of type-1 / 2 and 3. its undecidable for type-0 languages. $\endgroup$
    – heythere
    Commented May 14, 2022 at 18:33
  • 1
    $\begingroup$ Your question states "given a language $L$". There is no other hypothesis. $\endgroup$
    – Nathaniel
    Commented May 14, 2022 at 20:52
  • $\begingroup$ just updated the post $\endgroup$
    – heythere
    Commented May 14, 2022 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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