decidability

L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t ...

amitarp818

238 views

amitarp818 asked Dec 28, 2023

Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages

+ –

0 votes

1 answer

ajaysoni1924 asked Jul 15, 2019

852 views

Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$

$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \ri...

ajaysoni1924

852 views

ajaysoni1924 asked Jul 15, 2019

Theory of Computation
theory-of-computation
turing-machine
decidability
recursive-and-recursively-enumerable-languages

+ –

0 votes

0 answers

Na462 asked Jan 21, 2019

755 views

Reducible language ( Decidability)

Na462

755 views

Na462 asked Jan 21, 2019

Theory of Computation
theory-of-computation
decidability

+ –

0 votes

0 answers

Ayush Upadhyaya asked Jan 13, 2019

431 views

Decidability
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$ I was unable to get proof given in pdf above.Can anyone explain, if someone got it.

From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$I was unable to get...

Ayush Upadhyaya

431 views

Ayush Upadhyaya asked Jan 13, 2019

Theory of Computation
decidability
theory-of-computation

+ –

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

1 1 comment reply

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

1 1 comment