Hacker News Reader

Comment by vidarh | Hacker News Reader

Given that we know of no computable function that isn't Turing computable, and the set of Turing computable functions is known to be equivalent to the lambda calculus and equivalent to the set of general recursive functions, what is an immensely large hurdle would be to show even a single example of a computable function that is not Turing computable.

If you can do so, you'd have proven Turing, Kleen, Church, Goedel wrong, and disproven the Church-Turing thesis.

No such example is known to exist, and no such function is thought to be possible.

> Turing machines (and equivalents) are predicated on a finite alphabet / state space, which seems woefully inadequate to fully describe our clearly infinitary reality.

1/3 symbolically represents an infinite process. The notion that a finite alphabet can't describe inifity is trivially flawed.

View on HN

Function != Computable Function / general recursive function.

That's my point - computable functions are a [vanishingly] small subset of all functions.

For example (and close to our hearts!), the Halting Problem. There is a function from valid programs to halt/not-halt. This is clearly a function, as it has a well defined domain and co-domain, and produces the same output for the same input. However it is not computable!

For sure a finite alphabet can describe an infinity as you show - but not all infinity. For example almost all Real numbers cannot be defined/described with a finite string in a finite alphabet (they can of course be defined with countably infinite strings in a finite alphabet).

Non-computable functions are not relevant to this discussion, though, because humans can't compute them either, and so inherently an AGI need not be able to compute them.

The point remains that we know of no function that is computable to humans that is not in the Turing computable / general recursive function / lambda calculus set, and absent any indication that any such function is even possible, much less an example, it is no more reasonable to believe humans exceed the Turing computable than that we're surrounded by invisible pink unicorns, and the evidence would need to be equally extraordinary for there to be any reason to entertain the idea.

Humans do a lot of stuff that is hard to 'functionalise', computable or otherwise, so I'd say the burden of proof is on you. What's the function for creating a work of art? Or driving a car?

You clearly don't understand what a function means in this context, as the word function is not used in this thread in the way you appear to think it is used.

For starters, to have any hope of having a productive discussion on this subject, you need to understand what "function" mean in the context of the Church-Turing thesis (a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine -- note that not just "function" has a very specific meaning there, but also "effective method" does not mean what you're likely to read into it).

My original reframing was: the only way of showing that artificial intelligence can be constructed is by showing that humans cannot compute more than the Turing computable.

I was assuming the word 'compute' to have broader meaning than Turing computable - otherwise that statement is a tautology of course.

I pointed out that Turing computable functions are a (vanishingly) small subset of all possible functions - of which some may be 'computable' outside of Turing machines even if they are not Turing computable.

An example might be the three-body problem, which has no general closed-form solution, meaning there is no equation that always solves it. However our solar system seems to be computing the positions of the planets just fine.

Could it be that human sapience exists largely or wholly in that space beyond Turing computability? (by Church-Turing thesis the same as computable by effective method, as you point out). In which case your AGI project as currently conceived is doomed.

You don't need a closed-form solution to calculate trajectories with more precision than you can prove the universe uses.

I mean AI can already do those things

Reply on news.ycombinator.com