Non-reducibility of NIN to HBU for Baire class 2 functions
Non-reducibility of NIN to HBU for Baire class 2 functions
Let denote the problem of finding a function witnessing non-injectivity, and let denote the Heine–Borel theorem for covers of . Restrict the covers in to functions of Baire class ; also consider the full Lebesgue number lemma. Non-reducibility conjecture. The problem does not -reduce to restricted to Baire class functions, nor to the full Lebesgue number lemma. The conjecture is motivated by the preceding argument that post-processing is necessary because a Turing machine cannot evaluate a third-order functional at a point due to type restrictions. The source gives no resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Sam Sanders, “Between Turing and Kleene”, arXiv:2111.05052 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.