An Effective Procedure for Computing "Uncomputable" Functions
This work addresses foundational issues in computability theory by modeling aspects of reasoning beyond Turing machines, though it appears incremental as it builds on existing concepts like Gödel numbers and Turing-computable functions.
The paper tackles the problem of computing functions considered 'uncomputable' by Turing machines by introducing an effective procedure that outputs a natural number from any natural number input, using Turing-computable operations but with a second input that cannot be set to compute the output from the first input, thereby defining creative procedures for non-Turing-computable functions.
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.