An Effective Procedure for Computing "Uncomputable" Functions

Original · EN

We give an effective procedure that produces a natural number in its output from any natural number in its input, that is, it computes a total function. The elementary operations of the procedure are Turing-computable. The procedure has a second input which can contain the Goedel number of any Turing-computable total function whose range is a subset of the set of the Goedel numbers of all Turing-computable total functions. We prove that the second input cannot be set to the Goedel number of any Turing-computable function that computes the output from any natural number in its first input. In this sense, there is no Turing program that computes the output from its first input. The procedure is used to define creative procedures which compute functions that are not Turing-computable. We argue that creative procedures model an aspect of reasoning that cannot be modeled by Turing machines.