Non repeating complete list of partial recursive functions
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Is it possible to list all partial recursive functions such that every function appears only once in the enumeration. More precisely, does there exist (total) recursive function $f:mathbbN rightarrow mathbbN$ such that for any two different values $a,b in mathbbN$ (where $ane b$) the following two properties are satisfied:
(1) $phi_f(a) ne phi_f(b)$ (the two functions on the left and right hand side aren't the same)
(2) For any possible partial recursive function $g:mathbbN rightarrow mathbbN$ there exists some value $N in mathbbN$ such that $g=phi_f(N)$ (the two functions on the left and right hand side are the same)
$phi_x$ denotes the function computed by the program corresponding to index $x$ (under a reasonable 1-1 correspondence between the collection of programs and $mathbbN$).
computability
asked Aug 30 at 9:34
SSequence
29518
add a comment |Â
up vote
2
down vote
favorite
Is it possible to list all partial recursive functions such that every function appears only once in the enumeration. More precisely, does there exist (total) recursive function $f:mathbbN rightarrow mathbbN$ such that for any two different values $a,b in mathbbN$ (where $ane b$) the following two properties are satisfied:
(1) $phi_f(a) ne phi_f(b)$ (the two functions on the left and right hand side aren't the same)
(2) For any possible partial recursive function $g:mathbbN rightarrow mathbbN$ there exists some value $N in mathbbN$ such that $g=phi_f(N)$ (the two functions on the left and right hand side are the same)
$phi_x$ denotes the function computed by the program corresponding to index $x$ (under a reasonable 1-1 correspondence between the collection of programs and $mathbbN$).
computability
asked Aug 30 at 9:34
SSequence
29518
"Non repeating complete list" rather than "unique listing" may better describe it. Up to you.
– DanielV
Aug 30 at 10:02
This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem.
– Mark
Aug 30 at 13:05
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Is it possible to list all partial recursive functions such that every function appears only once in the enumeration. More precisely, does there exist (total) recursive function $f:mathbbN rightarrow mathbbN$ such that for any two different values $a,b in mathbbN$ (where $ane b$) the following two properties are satisfied:
(1) $phi_f(a) ne phi_f(b)$ (the two functions on the left and right hand side aren't the same)
(2) For any possible partial recursive function $g:mathbbN rightarrow mathbbN$ there exists some value $N in mathbbN$ such that $g=phi_f(N)$ (the two functions on the left and right hand side are the same)
$phi_x$ denotes the function computed by the program corresponding to index $x$ (under a reasonable 1-1 correspondence between the collection of programs and $mathbbN$).
computability
asked Aug 30 at 9:34
SSequence
29518
Is it possible to list all partial recursive functions such that every function appears only once in the enumeration. More precisely, does there exist (total) recursive function $f:mathbbN rightarrow mathbbN$ such that for any two different values $a,b in mathbbN$ (where $ane b$) the following two properties are satisfied:
(1) $phi_f(a) ne phi_f(b)$ (the two functions on the left and right hand side aren't the same)
(2) For any possible partial recursive function $g:mathbbN rightarrow mathbbN$ there exists some value $N in mathbbN$ such that $g=phi_f(N)$ (the two functions on the left and right hand side are the same)
$phi_x$ denotes the function computed by the program corresponding to index $x$ (under a reasonable 1-1 correspondence between the collection of programs and $mathbbN$).
computability
computability
asked Aug 30 at 9:34
SSequence
29518
asked Aug 30 at 9:34
SSequence
29518
edited Aug 30 at 11:12
asked Aug 30 at 9:34
SSequence
29518
asked Aug 30 at 9:34
SSequence
29518
asked Aug 30 at 9:34
SSequence
29518
29518
"Non repeating complete list" rather than "unique listing" may better describe it. Up to you.
– DanielV
Aug 30 at 10:02
This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem.
– Mark
Aug 30 at 13:05
add a comment |Â
"Non repeating complete list" rather than "unique listing" may better describe it. Up to you.
– DanielV
Aug 30 at 10:02
This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem.
– Mark
Aug 30 at 13:05
"Non repeating complete list" rather than "unique listing" may better describe it. Up to you.
– DanielV
Aug 30 at 10:02
"Non repeating complete list" rather than "unique listing" may better describe it. Up to you.
– DanielV
Aug 30 at 10:02
This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem.
– Mark
Aug 30 at 13:05
This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem.
– Mark
Aug 30 at 13:05
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
accepted
Yes, there is a total computable function with those properties. The existence was proved by Friedberg in 1958 using a priority argument.
Friedberg, Richard M. “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.†The Journal of Symbolic Logic, vol. 23, no. 3, 1958, pp. 309–316. JSTOR www.jstor.org/stable/2964290.
These uniformly computable non-repeating enumerations are called Friedberg numberings in the literature.
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
1
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Yes, there is a total computable function with those properties. The existence was proved by Friedberg in 1958 using a priority argument.
Friedberg, Richard M. “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.†The Journal of Symbolic Logic, vol. 23, no. 3, 1958, pp. 309–316. JSTOR www.jstor.org/stable/2964290.
These uniformly computable non-repeating enumerations are called Friedberg numberings in the literature.
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
1
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
add a comment |Â
up vote
3
down vote
accepted
Yes, there is a total computable function with those properties. The existence was proved by Friedberg in 1958 using a priority argument.
Friedberg, Richard M. “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.†The Journal of Symbolic Logic, vol. 23, no. 3, 1958, pp. 309–316. JSTOR www.jstor.org/stable/2964290.
These uniformly computable non-repeating enumerations are called Friedberg numberings in the literature.
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
1
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Yes, there is a total computable function with those properties. The existence was proved by Friedberg in 1958 using a priority argument.
Friedberg, Richard M. “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.†The Journal of Symbolic Logic, vol. 23, no. 3, 1958, pp. 309–316. JSTOR www.jstor.org/stable/2964290.
These uniformly computable non-repeating enumerations are called Friedberg numberings in the literature.
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
Yes, there is a total computable function with those properties. The existence was proved by Friedberg in 1958 using a priority argument.
Friedberg, Richard M. “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication.†The Journal of Symbolic Logic, vol. 23, no. 3, 1958, pp. 309–316. JSTOR www.jstor.org/stable/2964290.
These uniformly computable non-repeating enumerations are called Friedberg numberings in the literature.
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
edited Aug 30 at 14:21
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
answered Aug 30 at 14:14
Carl Mummert
64.2k7128239
64.2k7128239
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
1
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
add a comment |Â
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
1
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
Thanks, having a glance .... it seems that the last result there is exactly what I was asking. After posting this question, one other variant of this question also came to my mind. If we denote the set of partial recursive functions (1 input) as $P$ and the set of total recursive functions (1 input) as $R$ then does there exist a total computable function that enumerates (using indexes) every element of $P-R$ once and exactly once (original question was for $P$). Does that follow as a not-so-difficult corollary of the results/techniques in the paper (or is this question little different)?
– SSequence
Aug 30 at 14:43
1
1
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
The original article linked to in this answer is unfortunately spywalled, but a different (rather dense) two-page proof by M. Kummer (1990) is found at sciencedirect.com/science/article/pii/0304397590901414
– Henning Makholm
Aug 30 at 16:06
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@SSequence: The technique in the proof I linked to does extend directly to enumerating the non-total partial recursive functions without repetition.
– Henning Makholm
Aug 30 at 16:24
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@HenningMakholm Nice link .... sounds quite interesting that there are two different techniques for the same problem
– SSequence
Aug 30 at 16:32
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
@SSequence: The author I link to does credit Friedberg with a core idea in the proof, so "two different techniques" may be to oversell the difference. It's probably more of an incremental improvement -- though evidently enough of an improvement that TCS accepted the 1990 article.
– Henning Makholm
Aug 30 at 16:38
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2899317%2fnon-repeating-complete-list-of-partial-recursive-functions%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
"Non repeating complete list" rather than "unique listing" may better describe it. Up to you.
– DanielV
Aug 30 at 10:02
This would require a zero-test for partial recursive functions, which in turn would require a solution to the halting problem.
– Mark
Aug 30 at 13:05