Non-reducibility of NIN to HBU for Baire class 2 functions

From papers

Let NIN\textup{\textsf{NIN}} denote the problem of finding a function witnessing non-injectivity, and let HBU\textup{\textsf{HBU}} denote the Heine–Borel theorem for covers of [0,1][0,1]. Restrict the covers in HBU\textup{\textsf{HBU}} to functions of Baire class 22; also consider the full Lebesgue number lemma. Non-reducibility conjecture. The problem NIN\textup{\textsf{NIN}} does not NN-reduce to HBU\textup{\textsf{HBU}} restricted to Baire class 22 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

No solutions have been posted yet.