☃️merry chrimist☃️ on Nostr: MercurialBlack I just read Theorem 3.9 (Recursion Theorem) on page 8 here: ...
MercurialBlack (npub17z3…he6e) I just read Theorem 3.9 (Recursion Theorem) on page 8 here:
https://math.uchicago.edu/~may/REU2016/REUPapers/Wilson.pdf I'd summarize it as saying that, to get a function from N to a set X recursively, you first consider the set of all 'pseudo-graphs' of this function, which are subsets of N x X that are guaranteed to contain the actual graph. You consider the minimal 'pseudo-graph' (by taking intersection within N x X and then show that it is the correct graph. So the construction requires indexing over a set of subsets of N x X.
I'm not sure how general you want things, but I'd imagine that a similar idea of 'constructing the graph of the desired function / relation' would work
Published at
2024-01-26 07:15:37Event JSON
{
"id": "6475ecf6adea0d6632e4835c5702b5218a864c1ef8857199af45905d21c7be0a",
"pubkey": "0af5f8f4be4b08e199bf1fa4f01e4ab7dd35cd11a62afc72f251b7036c5a2eb8",
"created_at": 1706249737,
"kind": 1,
"tags": [
[
"p",
"f0a221fd8bc0629260b56340db7887c6258f13a4294e2f3a0cf952f5f880dcb3",
"wss://relay.mostr.pub"
],
[
"e",
"e3b6c3e8bc78e8ea0aca41b4ae6e2afd5b7dec99fdeab77a4bd67d0f0eb8dee4",
"wss://relay.mostr.pub",
"reply"
],
[
"proxy",
"https://cawfee.club/objects/3b74cfa9-dd4f-4601-8c33-9ed381b4ab68",
"activitypub"
]
],
"content": "nostr:npub17z3zrlvtcp3fyc94vdqdk7y8ccjc7yay998z7wsvl9f0t7yqmjes3uhe6e I just read Theorem 3.9 (Recursion Theorem) on page 8 here: https://math.uchicago.edu/~may/REU2016/REUPapers/Wilson.pdf I'd summarize it as saying that, to get a function from N to a set X recursively, you first consider the set of all 'pseudo-graphs' of this function, which are subsets of N x X that are guaranteed to contain the actual graph. You consider the minimal 'pseudo-graph' (by taking intersection within N x X and then show that it is the correct graph. So the construction requires indexing over a set of subsets of N x X. \n\nI'm not sure how general you want things, but I'd imagine that a similar idea of 'constructing the graph of the desired function / relation' would work",
"sig": "aa6226f4ff3ea75a2d4385752f06a1437b5f96d89ec0e674cc96b5240ba0a75aea0591a63f039e84cab168319ff78fe0d9b386086edad1ca4a0174aebb2fbbd9"
}