# undecidability – Variant of halting problem (and other not decidable problems)

It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable.

I have just thought of a variant approximation-like extension to this problem, that tries to “maximize” the correct answers an algorithm can make on this problem.

Formally speaking, let us say that an turing machine $$A$$ that always halts, is $$r$$-solving the halting problem, for $$r:mathbb{N}rightarrowmathbb{N}$$, if $$r(n)le |{xin Sigma^*mid xtext{ is a TM}spacelandspace|x|le nspace landspace A(x) text{ is correct}}|$$ where $$A(x)$$ is said to be correct $$iff$$ $$A(x)$$ outputs $$true$$ for $$xin HALT$$ and outputs $$false$$ otherwise.

Equivalently, we can define $$r$$ to be a function $$r:mathbb{N}rightarrow (0,1)$$ and then the requirement will change to $$ncdot r(n) le cdots$$

My question is: What is the largest $$r$$ function that we have an $$r$$-solving algorithm for? Or, what is the highest $$r$$ function that we can have an $$r$$-solving efficient (e.g. polynomial) algorithm for? Or are there other known things about the behavior of $$r$$-solving algorithms?

This can be easily adapted to any other problem, so I would be glad for any answer that explains this on any interesting language, and not necessarily the halting problem