I thought a bit about the question https://mathoverflow.net/q/503195/ and arrived at the following little problem of computability. Any ideas? It happens to involve something like the “parameterized realizability” from nprofile1qyt8wumn8ghj7un9d3shjtnyd968gmewwp6kytcqyz4g9497lls2ey4v3rxtld6a8m5rh7meav97tqfhnceyja6wn0lpgng99up (nprofile…99up)'s and nprofile1qyt8wumn8ghj7un9d3shjtnyd968gmewwp6kytcqyq0gte8xzp92t6508mavz7g8z37mv2c2n6sgfw5luws2j8m7nr7ez64kgh3 (nprofile…kgh3)'s paper https://arxiv.org/abs/2404.01256.
Let A, B ⊆ ℕ be disjoint. Assume that there is a program M which, given x ∈ A ∪ B, decides whether x ∈ A or x ∈ B, but with some help. Namely, there is a “desired oracle” which is an infinite word on four letters, and M has access to a “noisy” version of this oracle, which can be anything satisfying a requirement (that's the “parameterized” part: M must work given any oracle from a certain set; but unlike the countable reals paper, here the set will also depend on the input x). The requirement is the following: Arrange the four letters into a 2×2 table. Then if x ∈ A, the n-th letters of the desired and actual oracle must be on the same line of the table, while if x ∈ B they must be on the same column.
The question is: Must there be another program M' which does the same but without the help?
The difficulty is this: If M “knows” the n-th letter of the desired oracle (it manages to compute it somehow), and the n-th letter of the actual oracle is different, then M can deduce whether x ∈ A or x ∈ B. But if the actual oracle is the same as the desired one, then M can use that as computational power.
If I try to create M', I'd like to make it run M on well-chosen actual oracles. Those letters of the desired oracle which M “knows” should match in the actual oracle. But M' can't make everything match because it also has to work computably. So how to extract what exactly M knows in order to replicate it?
Jean Abou Samra (new account)
npub14p…htzwd
2025-12-06 23:26:34 UTC
Author Public Key
npub14pv6xjcsz2qa6tctew034s5wsj5p2xuh65q86qe6gpegaslstc6qjhtzwdPublished at
2025-12-06 23:26:34 UTCEvent JSON
{
"id": "68a8515150604b6f0922a3b0514c1c5149e1928962df6f0fabad4aff867e33b8",
"pubkey": "a859a34b101281dd2f0bcb9f1ac28e84a8151b97d5007d033a40728ec3f05e34",
"created_at": 1765063594,
"kind": 1,
"tags": [
[
"p",
"aa82d4beffe0ac92ac88ccbfb75d3ee83bfb79eb0be581379e3249774e9bfe14",
"wss://relay.ditto.pub/"
],
[
"p",
"1e85e4e6104aa5ea8f3efac17907147db62b0a9ea084ba9fe3a0a91f7e98fd91",
"wss://relay.ditto.pub/"
],
[
"p",
"a7cc877ed64ee1800329be962f831bde03345b008d86ce7dd446162a1848318f",
"wss://relay.ditto.pub/"
],
[
"p",
"406cda1605d9d95b1e39a78327c3891afba2baecd30a02b403c900e6d3f9bb58",
"wss://relay.ditto.pub/"
],
[
"proxy",
"https://mathstodon.xyz/users/jeanas/statuses/115675207720171604",
"activitypub"
],
[
"client",
"Mostr",
"31990:6be38f8c63df7dbf84db7ec4a6e6fbbd8d19dca3b980efad18585c46f04b26f9:mostr",
"wss://relay.ditto.pub/"
]
],
"content": "I thought a bit about the question https://mathoverflow.net/q/503195/ and arrived at the following little problem of computability. Any ideas? It happens to involve something like the “parameterized realizability” from nostr:nprofile1qyt8wumn8ghj7un9d3shjtnyd968gmewwp6kytcqyz4g9497lls2ey4v3rxtld6a8m5rh7meav97tqfhnceyja6wn0lpgng99up's and nostr:nprofile1qyt8wumn8ghj7un9d3shjtnyd968gmewwp6kytcqyq0gte8xzp92t6508mavz7g8z37mv2c2n6sgfw5luws2j8m7nr7ez64kgh3's paper https://arxiv.org/abs/2404.01256.\n\nLet A, B ⊆ ℕ be disjoint. Assume that there is a program M which, given x ∈ A ∪ B, decides whether x ∈ A or x ∈ B, but with some help. Namely, there is a “desired oracle” which is an infinite word on four letters, and M has access to a “noisy” version of this oracle, which can be anything satisfying a requirement (that's the “parameterized” part: M must work given any oracle from a certain set; but unlike the countable reals paper, here the set will also depend on the input x). The requirement is the following: Arrange the four letters into a 2×2 table. Then if x ∈ A, the n-th letters of the desired and actual oracle must be on the same line of the table, while if x ∈ B they must be on the same column.\n\nThe question is: Must there be another program M' which does the same but without the help?\n\nThe difficulty is this: If M “knows” the n-th letter of the desired oracle (it manages to compute it somehow), and the n-th letter of the actual oracle is different, then M can deduce whether x ∈ A or x ∈ B. But if the actual oracle is the same as the desired one, then M can use that as computational power.\n\nIf I try to create M', I'd like to make it run M on well-chosen actual oracles. Those letters of the desired oracle which M “knows” should match in the actual oracle. But M' can't make everything match because it also has to work computably. So how to extract what exactly M knows in order to replicate it?",
"sig": "edd8fffa09495e959e27d5fba8ef7ae2b5560a25a97980e3eceef2eccc0231ca4f364c511875dcb6ced900b873f9d37f8219356507b3dbdcf47238606a439315"
}