Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them? [duplicate]

-1

$begingroup$

This question is an exact duplicate of:

• 
  is the set {i | Dom($phi_i$) = ∅} recursive, recursive enumerable or none of them
  

Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?

We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}.

Thank you for your help

computability

share|cite|improve this question

asked Jan 7 at 13:29

NormanNorman

177

$endgroup$

marked as duplicate by Carl Mummert, Noah Schweber, Glorfindel, Lee David Chung Lin, KReiser Jan 8 at 1:38

This question was marked as an exact duplicate of an existing question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
  $endgroup$
  – Carl Mummert
  Jan 7 at 14:02
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is an exact duplicate of your previous question, unless I'm missing something. Don't do that.
  $endgroup$
  – Noah Schweber
  Jan 7 at 14:35
  
  
  

  
  
  
  

add a comment | 

-1

$begingroup$

This question is an exact duplicate of:

• 
  is the set {i | Dom($phi_i$) = ∅} recursive, recursive enumerable or none of them
  

Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?

We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}.

Thank you for your help

computability

share|cite|improve this question

asked Jan 7 at 13:29

NormanNorman

177

$endgroup$

marked as duplicate by Carl Mummert, Noah Schweber, Glorfindel, Lee David Chung Lin, KReiser Jan 8 at 1:38

This question was marked as an exact duplicate of an existing question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
  $endgroup$
  – Carl Mummert
  Jan 7 at 14:02
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is an exact duplicate of your previous question, unless I'm missing something. Don't do that.
  $endgroup$
  – Noah Schweber
  Jan 7 at 14:35
  
  
  

  
  
  
  

add a comment | 

-1

-1

-1

$begingroup$

This question is an exact duplicate of:

• 
  is the set {i | Dom($phi_i$) = ∅} recursive, recursive enumerable or none of them
  

Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?

We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}.

Thank you for your help

computability

share|cite|improve this question

asked Jan 7 at 13:29

NormanNorman

177

$endgroup$

This question is an exact duplicate of:

• 
  is the set {i | Dom($phi_i$) = ∅} recursive, recursive enumerable or none of them
  

Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?

We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}.

Thank you for your help

This question is an exact duplicate of:

• 
  is the set {i | Dom($phi_i$) = ∅} recursive, recursive enumerable or none of them
  

computability

computability

share|cite|improve this question

asked Jan 7 at 13:29

NormanNorman

177

share|cite|improve this question

asked Jan 7 at 13:29

NormanNorman

177

share|cite|improve this question

share|cite|improve this question

asked Jan 7 at 13:29

NormanNorman

177

asked Jan 7 at 13:29

NormanNorman

177

asked Jan 7 at 13:29

NormanNorman

177

177

marked as duplicate by Carl Mummert, Noah Schweber, Glorfindel, Lee David Chung Lin, KReiser Jan 8 at 1:38

This question was marked as an exact duplicate of an existing question.

marked as duplicate by Carl Mummert, Noah Schweber, Glorfindel, Lee David Chung Lin, KReiser Jan 8 at 1:38

This question was marked as an exact duplicate of an existing question.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
  $endgroup$
  – Carl Mummert
  Jan 7 at 14:02
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is an exact duplicate of your previous question, unless I'm missing something. Don't do that.
  $endgroup$
  – Noah Schweber
  Jan 7 at 14:35
  
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
  $endgroup$
  – Carl Mummert
  Jan 7 at 14:02
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This is an exact duplicate of your previous question, unless I'm missing something. Don't do that.
  $endgroup$
  – Noah Schweber
  Jan 7 at 14:35
  
  
  

  
  
  
  

$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Jan 7 at 14:02

$begingroup$
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc.
$endgroup$
– Carl Mummert
Jan 7 at 14:02

1

1

$begingroup$
This is an exact duplicate of your previous question, unless I'm missing something. Don't do that.
$endgroup$
– Noah Schweber
Jan 7 at 14:35

$begingroup$
This is an exact duplicate of your previous question, unless I'm missing something. Don't do that.
$endgroup$
– Noah Schweber
Jan 7 at 14:35

add a comment | 

1 Answer
1

active

oldest

votes

0

$begingroup$

The set is not recursively enumerable.

The theorem of Rice-Shapiro says: Let $A$ be a class of monadic partial recursive functions whose corresponding index set $${rm prog}(A) = {xin{Bbb N}_0mid phi_xin A}$$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g in A$ (i.e., $g$ has finite domain) such that $g subseteq f$ (i.e., $f$ is an extension of $g$).

If the nowhere-defined function $f_uparrow$ lies in $A$, then all monadic partial recursive functions lie in $A$. Indeed, each monadic computable function extends the nowhere-defined function and so by the theorem of Rice-Shaprio lies in $A$. This is not the case.

share|cite|improve this answer

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

$endgroup$

add a comment | 

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

0

$begingroup$

The set is not recursively enumerable.

The theorem of Rice-Shapiro says: Let $A$ be a class of monadic partial recursive functions whose corresponding index set $${rm prog}(A) = {xin{Bbb N}_0mid phi_xin A}$$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g in A$ (i.e., $g$ has finite domain) such that $g subseteq f$ (i.e., $f$ is an extension of $g$).

If the nowhere-defined function $f_uparrow$ lies in $A$, then all monadic partial recursive functions lie in $A$. Indeed, each monadic computable function extends the nowhere-defined function and so by the theorem of Rice-Shaprio lies in $A$. This is not the case.

share|cite|improve this answer

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

$endgroup$

add a comment | 

0

$begingroup$

The set is not recursively enumerable.

The theorem of Rice-Shapiro says: Let $A$ be a class of monadic partial recursive functions whose corresponding index set $${rm prog}(A) = {xin{Bbb N}_0mid phi_xin A}$$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g in A$ (i.e., $g$ has finite domain) such that $g subseteq f$ (i.e., $f$ is an extension of $g$).

If the nowhere-defined function $f_uparrow$ lies in $A$, then all monadic partial recursive functions lie in $A$. Indeed, each monadic computable function extends the nowhere-defined function and so by the theorem of Rice-Shaprio lies in $A$. This is not the case.

share|cite|improve this answer

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

$endgroup$

add a comment | 

0

0

0

$begingroup$

The set is not recursively enumerable.

The theorem of Rice-Shapiro says: Let $A$ be a class of monadic partial recursive functions whose corresponding index set $${rm prog}(A) = {xin{Bbb N}_0mid phi_xin A}$$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g in A$ (i.e., $g$ has finite domain) such that $g subseteq f$ (i.e., $f$ is an extension of $g$).

If the nowhere-defined function $f_uparrow$ lies in $A$, then all monadic partial recursive functions lie in $A$. Indeed, each monadic computable function extends the nowhere-defined function and so by the theorem of Rice-Shaprio lies in $A$. This is not the case.

share|cite|improve this answer

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

$endgroup$

The set is not recursively enumerable.

The theorem of Rice-Shapiro says: Let $A$ be a class of monadic partial recursive functions whose corresponding index set $${rm prog}(A) = {xin{Bbb N}_0mid phi_xin A}$$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g in A$ (i.e., $g$ has finite domain) such that $g subseteq f$ (i.e., $f$ is an extension of $g$).

If the nowhere-defined function $f_uparrow$ lies in $A$, then all monadic partial recursive functions lie in $A$. Indeed, each monadic computable function extends the nowhere-defined function and so by the theorem of Rice-Shaprio lies in $A$. This is not the case.

share|cite|improve this answer

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

share|cite|improve this answer

share|cite|improve this answer

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

answered Jan 7 at 13:44

WuestenfuxWuestenfux

4,2491413

4,2491413

add a comment | 

add a comment | 

This page is only for reference, If you need detailed information, please check here