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

About 5 years old · traced to

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.

References

Primary source

Sam Sanders, “Between Turing and Kleene”, arXiv:2111.05052 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.