Editing Church–Turing thesis (section)

== Non-computable functions ==
{{One source section|date=November 2017}}
One can formally define functions that are not computable. A well-known example of such a function is the [[Busy Beaver]] function. This function takes an input ''n'' and returns the largest number of symbols that a [[Turing machine]] with ''n'' states can print before halting, when run with no input. Finding an upper bound on the busy beaver function is equivalent to solving the [[halting problem]], a problem known to be unsolvable by Turing machines. Since the busy beaver function cannot be computed by Turing machines, the Church–Turing thesis states that this function cannot be effectively computed by any method.

Several computational models allow for the computation of (Church-Turing) non-computable functions. These are known as
[[hypercomputation|hypercomputers]].
Mark Burgin argues that [[super-recursive algorithm]]s such as inductive Turing machines disprove the Church–Turing thesis.<ref>{{cite book |last=Burgin |first=Mark |date=2005 |title=Super-Recursive Algorithms |series=Monographs in Computer Science |publisher=Springer |location=New York |isbn=978-0-387-95569-8 |oclc=990755791 }}</ref>{{page needed|date=November 2017}} His argument relies on a definition of algorithm broader than the ordinary one, so that non-computable functions obtained from some inductive Turing machines are called computable. This interpretation of the Church–Turing thesis differs from the interpretation commonly accepted in computability theory, discussed above. The argument that super-recursive algorithms are indeed algorithms in the sense of the Church–Turing thesis has not found broad acceptance within the computability research community.{{citation needed|date=May 2020}}