A noncomputable function is a function that is not a computable function. For a total
function on the nonnegative integers,
this means that no Turing machine halts with output
for every input
. For a partial
function, computability additionally requires the Turing
machine not to halt on inputs outside its domain.
The characteristic function of an undecidable set is noncomputable.
Noncomputable Function
See also
Computable Function, Halting Problem, Noncomputable Number, UndecidableExplore with Wolfram|Alpha
References
Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 42, 230-265, 1937.Cite this as:
Weisstein, Eric W. "Noncomputable Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NoncomputableFunction.html