[roywiggins]

> To conclude, we can never automate the construction (nor the testing) of computer programs. So says logic and so says the theory of computation.

On the other hand, the strong Church-Turing thesis is that nothing is more powerful than a Turing machine when it comes to solving halting problems, including humans. This is not proven or really provable but it seems more likely than not (humans certainly don't seem especially good at solving halting problems in general).

If the Church-Turing thesis is true (at least as applied to humans), discovering valid, halting programs by heuristic using a machine isn't barred by the halting problem as far as I can tell.

In other words, humans almost certainly aren't solving halting problems when they program, why should computers necessarily have to? Humans mess up and produce programs that don't halt or don't produce the output they expect all the time, but we still produce useful programs at least sometimes, even if we can't know for sure which programs are which.

[avsteele]

Exactly.

I'm very surprised someone a whole essay like this and have this misconception.

I was half expecting to see "humans building something smarter than human machines violates the laws of thermodynamics" next.

[SamBam]

Indeed. It reminds me of Penrose in The Emperor's New Mind (or one of his other books), where a large chunk of his argument that human consciousness and understanding can't be fully explained by computational processes, because humans can understand and see the truth of certain statements that formal systems cannot.

Mathematicians have spilled a bunch of ink explaining why Penrose didn't understand Godel's proof.

[omnicognate]

The linked article is ridiculous, but your comment is a misrepresentation of the Penrose debate. The main weak point of Penrose's argument isn't that he "didn't understand Godel's proof". He rightly observed that Godel's incompleteness theorem requires that either human minds are capable of things algorithms are not capable of, or that their perception of mathematical truth is limited in certain ways, an observation that Godel himself made. The main point of disagreement with his critics is not the mechanics of Godel's theorem which, unsurprisingly, this Nobel prize winning mathematician (*) understands perfectly well, but whether human perception of mathematical truth is limited in these ways.

The question of whether human perception of mathematical truth is infallible is open to philosophical debate. Penrose distinguishes between mistakes, which all mathematicians make but which in principle they can later come to recognise as mistakes, and true incorrect perception of mathematical truth, where no amount of checking, re-derivation, etc. could possibly right the incorrect perception. His view is that the latter type of error does not exist, that there is a mathematical ground truth that we can directly perceive and that is infallible, and that the mistakes made by mathematicians are of a different nature to inconsistencies in that perception of mathematical ground truth.

Penrose went too far in presenting this argument as a proof of the impossibility of strong AI based on algorithms. The point about human perception of mathematical truth can very reasonably be disputed, and is part of a much larger debate about the fundamental nature of maths that is far from settled. Personally, though, my intuition is that Penrose is right about the human perception of mathematical truth, and I therefore find the Godel-based argument persuasive. It's not a proof because it rests on an assumption that has not been proven, but I find it convincing to the extent that I tend to think that the assumption is probably true.

So the debate is a philosophical one more than it is a mathematical one, and while Penrose may be guilty of some rather bad PR, accusing him of "not understanding Godel's proof" does him a disservice.

* Yes, there's no Nobel prize in mathematics, but he is a mathematician (as well as a physicist) and he has won a Nobel prize.

[mistermann]

Could you possibly expand on this?

> He rightly observed that Godel's incompleteness theorem requires that either human minds are capable of things algorithms are not capable of...

[sdwr]

Not OP, feel free to correct me, but Godel proved that any formal system of logic can be shown to be logically inconsistent at at least one point.

"Formal system of logic" maps well onto Turing machines, and Turing machines map onto "any computer system" if you are very abstract about it.

Now, people are wrong about mathematical facts, but seemingly not forever. We puzzle it over, come back to it, someone makes a breakthrough. It doesn't seem like there is a fixed blind spot where our logic breaks down.

So what are people doing that is not captured by a formal system of logic?

Options:

1. The mapping of Turing machines to computers isn't airtight - they are doing something "more" than a TM with infinite time + space is capable of

2. People are not "more than" an infinite TM either, we just romantically believe we are, and ignore our own flaws

3. People are doing something special that is not captured by our theory of computation

[roywiggins]

> Godel proved that any formal system of logic can be shown to be logically inconsistent at at least one point.

He proved they can be inconsistent, or incomplete. The ones that mathematicians work with are incomplete and assumed to be consistent[0], namely that there are statements which are true, but not provable, within that system. Consistent-but-incomplete systems don't have any contradictions or logical holes; they just can't determine the truth of every possible statement.

From an incomplete system you can build a "more powerful" system- one with another axiom that makes more things provable without contradicting anything in the original one.

In inconsistent systems, everything is provable, even statements' own negations, so they aren't very useful.

[0] one statement that you can't prove within a (sufficiently powerful) system is "this system is consistent."

[zer00eyz]

>> but any talk of fully automating human intuition (Turing’s Oracle!) in coming up with novel solutions to complex problems is fantasy and the computer science police department (CSPD) should issue a citation for any such talk.

You and I both intuit that there are conjectures that, likely, do not have a solution. The author is proposing (and maybe rightly) that an AI as a Turing machine with this intuition would inherently (have to) be a Turing Oracle...

It's an interesting take that has some implications...

[aSanchezStern]

Err, only if humans have to be turing oracles to have that intuition, right? Plus, the halting problem only says that you can't have a procedure which will be 100% right on 100% of programs about whether or not they halt. Relax either of those 100%s, and it becomes possible again, just like how human intuition can be right about things 90% of the time, even if those things can't possibly be predicted 100% of the time.

[zer00eyz]

Are people Turing machines is a question...

> Plus, the halting problem only says that you can't have a procedure which will be 100% right on 100% of programs about whether or not they halt.

Your missing it still...

"Given a computer program and an input, will the program terminate or will it run forever?"

We both know that the collatz conjecture likely wont ever halt. We understand that. WE are reasonable oracles. Now write me an oracle that can detect this. Dont feed a list of problems to avoid, write a program that detects these types problems and skips them... Hint, you likley cant. You could simulate one, but that would be cheating...

A real AI needs this, or needs to be able to do it, or it risks working on the collatz conjecture till the heat death of the universe, or till it consumes the universe in a paperclip style problem...

The implication is that real ai might not come out of a Turing machine ever...

[roywiggins]

The implication of the article isn't that you can't produce a Turing oracle, it's that it's mathematically impossible to ever replace programmers with computers at all.

The latter claim doesn't follow: programmers aren't Turing oracles either. A programming machine that can emulate whatever humans are doing when they program, would be able to program too.

[af3d]

FWIW the Collatz conjecture actually asserts the exact opposite, that the sequence always terminates.

[oasisaimlessly]

> We both know that the collatz conjecture likely wont ever halt.

Speak for yourself. I know that the Collatz Conjecture is an unsolved problem and so wouldn't make any strong statements about it.

[viccis]

I got a flashback to Zed Shaw's infamous Turing completeness quip about Python 3, except that at least his was really just a stupid joke. Here, the author is using a motte-and-bailey fallacy in which he attacks a more complex and open ended statement ("AI will Soon Replace Programmers") by instead retreating to a more straightforward and falsifiable statement (the ability to write any computer program).

[mmoskal]

I guess the short way to say it is that "undecidable" doesn't mean "it can't ever be decided", just not always.

And of course all programs of practical significance are finite state machines (since there is only a finite number of atoms in the universe).

[XorNot]

Isn't the point closer to, humans simply go "hey that seems to be taking a little long?" when a program doesn't halt, so why couldn't a machine? Basically a fairly obvious constraint on the solution space is "completes in less then N wall-clock time".

[roywiggins]

You can definitely detect a portion of halting machines this way, but it's probably a relatively small portion because the Busy Beaver numbers grow inconceivably quickly: the longest-running machines that halt can go practically forever, you'd need more time than the universe has negentropy left to detect them.

[mlyle]

Came here to write this, was glad to see it's already here.

All the limits that exist for computing machines almost certainly exist for us too; we don't need to solve the halting problem; we don't solve large NP-hard problems; etc.

Of course, if one believes there's something mystical about brains -- whether a soul or access to quantum computing -- perhaps one would disagree.

[soist]

The brain is not a computer. Computation is an abstraction of thinking but it does not coincide with it.

[aSanchezStern]

This is a particular philosophical conjecture, not a proven scientific fact. We don't understand enough about the human brain to prove whether it is fundamentally different from a very complex computer.

[roywiggins]

My intuition is that we probably should assume they're different until proven otherwise, but also that brains are probably not Turing oracles either.

[roywiggins]

I think this is quite possible, but it doesn't imply that the strong Church-Turing thesis isn't true: brains could still be Turing equivalent to computers, in that neither would be able to solve the halting problem for the other (at least insofar as humans have a "halting problem", which maybe we don't, but you could formulate other things like predicting behavior, which in standard computation is also Turing complete usually)

Since humans don't seem to be particularly good at solving the halting problem even for very small TMs, it doesn't seem that likely to me that we are categorically stronger at it than computers, whether our cognition is truly "computation" or not.

[Kinrany]

There's only one halting problem.