Try finding languages such that L1⊆L2⊆L3 where L1,L3∉ RE and L2∈ R [duplicate]
$begingroup$
This question is an exact duplicate of:
Finding languages such that $L_{1} subseteq L_{2} subseteq L_{3}$ where $L_{1}, L_{3} notin mathbb{R}$, $L_{2} in mathbb{R}$
1 answer
"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
computability automata
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
$endgroup$
marked as duplicate by Asaf Karagila♦ Jan 17 at 13:04
This question was marked as an exact duplicate of an existing question.
add a comment |
$begingroup$
This question is an exact duplicate of:
Finding languages such that $L_{1} subseteq L_{2} subseteq L_{3}$ where $L_{1}, L_{3} notin mathbb{R}$, $L_{2} in mathbb{R}$
1 answer
"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
computability automata
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
$endgroup$
marked as duplicate by Asaf Karagila♦ Jan 17 at 13:04
This question was marked as an exact duplicate of an existing question.
$begingroup$
"RE" here means "recursively enumerable" and "R" means "recursive"?
$endgroup$
– MJD
Jan 10 at 15:49
$begingroup$
yes. "RE" means "recursively enumerable" and "R" means "recursive
$endgroup$
– Ofir Cohen
Jan 10 at 15:54
add a comment |
$begingroup$
This question is an exact duplicate of:
Finding languages such that $L_{1} subseteq L_{2} subseteq L_{3}$ where $L_{1}, L_{3} notin mathbb{R}$, $L_{2} in mathbb{R}$
1 answer
"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
computability automata
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
$endgroup$
This question is an exact duplicate of:
Finding languages such that $L_{1} subseteq L_{2} subseteq L_{3}$ where $L_{1}, L_{3} notin mathbb{R}$, $L_{2} in mathbb{R}$
1 answer
"RE" means "recursively enumerable" and "R" means "recursive. i am looking for the simplest solution- using a known languages such that do not demand another formal proof.
This question is an exact duplicate of:
Finding languages such that $L_{1} subseteq L_{2} subseteq L_{3}$ where $L_{1}, L_{3} notin mathbb{R}$, $L_{2} in mathbb{R}$
1 answer
computability automata
computability automata
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
asked Jan 10 at 20:02
Ofir CohenOfir Cohen
111
111
marked as duplicate by Asaf Karagila♦ Jan 17 at 13:04
This question was marked as an exact duplicate of an existing question.
marked as duplicate by Asaf Karagila♦ Jan 17 at 13:04
This question was marked as an exact duplicate of an existing question.
$begingroup$
"RE" here means "recursively enumerable" and "R" means "recursive"?
$endgroup$
– MJD
Jan 10 at 15:49
$begingroup$
yes. "RE" means "recursively enumerable" and "R" means "recursive
$endgroup$
– Ofir Cohen
Jan 10 at 15:54
add a comment |
$begingroup$
"RE" here means "recursively enumerable" and "R" means "recursive"?
$endgroup$
– MJD
Jan 10 at 15:49
$begingroup$
yes. "RE" means "recursively enumerable" and "R" means "recursive
$endgroup$
– Ofir Cohen
Jan 10 at 15:54
$begingroup$
"RE" here means "recursively enumerable" and "R" means "recursive"?
$endgroup$
– MJD
Jan 10 at 15:49
$begingroup$
"RE" here means "recursively enumerable" and "R" means "recursive"?
$endgroup$
– MJD
Jan 10 at 15:49
$begingroup$
yes. "RE" means "recursively enumerable" and "R" means "recursive
$endgroup$
– Ofir Cohen
Jan 10 at 15:54
$begingroup$
yes. "RE" means "recursively enumerable" and "R" means "recursive
$endgroup$
– Ofir Cohen
Jan 10 at 15:54
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Let $widetilde{L}notinmbox{RE}$ have alphabet $widetilde{Sigma}$. We define $Sigma:={0,1}timeswidetilde{Sigma}$. Then for $iin{0,1}$ we define $widetilde{L_i}:={(i,c_1)(i,c_2)...(i,c_n):c_1c_2...c_ninwidetilde{L}}notinmbox{RE}$. We can consider the languages $L_1:=widetilde{L_0}$, $L_2:=({0}timeswidetilde{Sigma})^*$ and $L_3:=L_2cupwidetilde{L_1}$ which have alphabet $Sigma$. We get $L_1subseteq L_2subseteq L_3$ and $L_1,L_3notinmbox{RE}$, but $L_2inmbox{R}$.
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
$endgroup$
add a comment |
$begingroup$
Let $H$ be a suitably chosen non-RE set and let $R$ be recursive. Then $$Hcap R subsetneq Rsubsetneq Hcup R.$$
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $widetilde{L}notinmbox{RE}$ have alphabet $widetilde{Sigma}$. We define $Sigma:={0,1}timeswidetilde{Sigma}$. Then for $iin{0,1}$ we define $widetilde{L_i}:={(i,c_1)(i,c_2)...(i,c_n):c_1c_2...c_ninwidetilde{L}}notinmbox{RE}$. We can consider the languages $L_1:=widetilde{L_0}$, $L_2:=({0}timeswidetilde{Sigma})^*$ and $L_3:=L_2cupwidetilde{L_1}$ which have alphabet $Sigma$. We get $L_1subseteq L_2subseteq L_3$ and $L_1,L_3notinmbox{RE}$, but $L_2inmbox{R}$.
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
$endgroup$
add a comment |
$begingroup$
Let $widetilde{L}notinmbox{RE}$ have alphabet $widetilde{Sigma}$. We define $Sigma:={0,1}timeswidetilde{Sigma}$. Then for $iin{0,1}$ we define $widetilde{L_i}:={(i,c_1)(i,c_2)...(i,c_n):c_1c_2...c_ninwidetilde{L}}notinmbox{RE}$. We can consider the languages $L_1:=widetilde{L_0}$, $L_2:=({0}timeswidetilde{Sigma})^*$ and $L_3:=L_2cupwidetilde{L_1}$ which have alphabet $Sigma$. We get $L_1subseteq L_2subseteq L_3$ and $L_1,L_3notinmbox{RE}$, but $L_2inmbox{R}$.
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
$endgroup$
add a comment |
$begingroup$
Let $widetilde{L}notinmbox{RE}$ have alphabet $widetilde{Sigma}$. We define $Sigma:={0,1}timeswidetilde{Sigma}$. Then for $iin{0,1}$ we define $widetilde{L_i}:={(i,c_1)(i,c_2)...(i,c_n):c_1c_2...c_ninwidetilde{L}}notinmbox{RE}$. We can consider the languages $L_1:=widetilde{L_0}$, $L_2:=({0}timeswidetilde{Sigma})^*$ and $L_3:=L_2cupwidetilde{L_1}$ which have alphabet $Sigma$. We get $L_1subseteq L_2subseteq L_3$ and $L_1,L_3notinmbox{RE}$, but $L_2inmbox{R}$.
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
$endgroup$
Let $widetilde{L}notinmbox{RE}$ have alphabet $widetilde{Sigma}$. We define $Sigma:={0,1}timeswidetilde{Sigma}$. Then for $iin{0,1}$ we define $widetilde{L_i}:={(i,c_1)(i,c_2)...(i,c_n):c_1c_2...c_ninwidetilde{L}}notinmbox{RE}$. We can consider the languages $L_1:=widetilde{L_0}$, $L_2:=({0}timeswidetilde{Sigma})^*$ and $L_3:=L_2cupwidetilde{L_1}$ which have alphabet $Sigma$. We get $L_1subseteq L_2subseteq L_3$ and $L_1,L_3notinmbox{RE}$, but $L_2inmbox{R}$.
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
answered Jan 10 at 20:56
SmileyCraftSmileyCraft
3,776519
3,776519
add a comment |
add a comment |
$begingroup$
Let $H$ be a suitably chosen non-RE set and let $R$ be recursive. Then $$Hcap R subsetneq Rsubsetneq Hcup R.$$
$endgroup$
add a comment |
$begingroup$
Let $H$ be a suitably chosen non-RE set and let $R$ be recursive. Then $$Hcap R subsetneq Rsubsetneq Hcup R.$$
$endgroup$
add a comment |
$begingroup$
Let $H$ be a suitably chosen non-RE set and let $R$ be recursive. Then $$Hcap R subsetneq Rsubsetneq Hcup R.$$
$endgroup$
Let $H$ be a suitably chosen non-RE set and let $R$ be recursive. Then $$Hcap R subsetneq Rsubsetneq Hcup R.$$
answered Jan 10 at 21:33
community wiki
MJD
add a comment |
add a comment |
$begingroup$
"RE" here means "recursively enumerable" and "R" means "recursive"?
$endgroup$
– MJD
Jan 10 at 15:49
$begingroup$
yes. "RE" means "recursively enumerable" and "R" means "recursive
$endgroup$
– Ofir Cohen
Jan 10 at 15:54