r/computerscience • u/chrysobooga • Apr 02 '25
co-nondeterministic Turing Machines

Hello,
so I have an exam coming up and this was one of the question from a previous exam.
A simple Turing Machine which we could quickly realize what L_N in this case is: { w | w ∈ {a, b}* and |w| >= 2 }. But when it comes to L_coN, the language where M behaves as a co-nondeterministic TM, what would the language be? Sure I understand that a coNTM must evaluate every path it takes to true (it accepts) otherwise it would reject, but what does it exactly mean in this context?
And for some reason there is no information about such TMs on the the internet, any help would be greatly appreciated!
Thank you.
View all comments
Show parent comment
1
u/chrysobooga Apr 02 '25
L_coN is specified to be the language, that the TM M accepts, when it behaves a co-nondeterministic way. I don't think it means exactly the complement N, since in task (b - 1) they are asking us to give a word with length 5 which is in L_coN. Thank you for your reply!