I'm finding it difficult to locate the languages $L_1$ and $L_2$ in the arithmetic hierarchy. If anyone could explain which class they're in an why that would be great. Thanks in advance.

$L_1$ = {$<w,v>$ : exist u s.t. $|u| > |v|$, accepted by the Turing Machine $M_w$}

$L_2$ = {$<w,v>$ : $M_w$ accepts all string of size $> 2|v|$}


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.