[Udik]

According to Wikipedia:

"the [Church-Turing] thesis has several possible meanings:

1) The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics."

[Aardwolf]

What is meant by "non-recursive functions" here?

From my knowledge a non-recursive function would be easier than a recursive one, since a non-recursive one will not call itself while a recursive one can. But the quoted phrase seems to imply it must be something more difficult instead...

Problem is, wikipedia's page https://en.wikipedia.org/wiki/Non-recursive_function does not define it either, it just redirects you to the recursion page (though not recursively, so wikipedia did not go for the joke) which does not define it either.

[klmr]

Non-recursive in this context means functions that aren’t computationally equivalent to those computable by recursive functions only [1]. This is equivalent to Turing completeness. It’s the second & third meaning in your link.

A “non-recursive function” would be more powerful than that; or, conversely, it would be a function which cannot be computed using a Turing machine. Alternatively, these are also know as super-recursive functions [2].

[1] https://en.wikipedia.org/wiki/Computable_function [2] https://en.wikipedia.org/wiki/Super-recursive_algorithm

[Aardwolf]

Thanks for the explanation! Neither of the two linked articles mention the term "non-recursive" by the way, so it's thanks to your response I know it's a synonym of super-recursive, not thanks to wikipedia.