What does it mean for a function to be Turing computable?
In the context of automata theory, a function is considered Turing computable if there exists a Turing machine capable of computing it.1
A Turing machine represents a function that maps natural numbers to natural numbers. To calculate , the machine is provided with a tape containing consecutive 1s. The machine is said to compute the function if, for every input , it stops after a finite number of steps with consecutive 1s on its tape, such that . If the machine fails to stop for a given value of , the function is considered undefined for that input.1
This definition is central to the foundations of mathematics and is equivalent to other formalizations of effective computability, such as partial recursive functions. The concept relies on Church’s thesis, which posits that these formal definitions successfully capture the intuitive, pretheoretical notion of an effectively mechanical procedure.123