That's a pretty simplistic view. How do you know we can't determine whether an arbitrary program will halt or not (assuming access to all inputs and enough time to examine it)? What in principle would prevent us from doing so? But computers in principle cannot, since the problem is often non-algorithmic.
For example, consider the following program, which is passed the text of the file it is in as input:
function doesHalt($program, $inputs): bool {...}
$input = $argv[0]; // contents of this file
if (doesHalt($input, [$input])) {
while(true) {
print "Wrong! It doesn't halt!";
}
} else {
print "Wrong! It halts!";
}
Can you tell me if a program which searches for counterexamples to the Collatz conjecture halts?
Turing's entire analysis started from the point of what humans could do.
Your argument doesn't disprove my assumption *. In which case, what's the point of it?
* - I don't necessarily believe this assumption. But I do dislike bad arguments.
func main() {
var n = 4;
OUTER: loop {
for (var i = 2; i < n/2; i++) {
if (isPrime(i) && isPrime(n-i)) {
n += 2;
continue OUTER; // Goldbach’s conjecture
}
break;
}
}And while the human brain might not be a bio-computer, I'm not sure, its computational prowess are doubtfully stronger than a quantum turing machine, which can't solve the halting problem either.
It doesn't matter what the algorithmic doesHalt function returns - it will always be incorrect for this program. What makes you certain there is an algorithmic analog for all human reasoning?
The function we are trying to compute is undecidable. Sure we as humans understand that there's a dichotomy here: if the program halts it won't halt; if it doesn't halt it will halt. But the function we are asked to compute must have one output on a given input. So a human, when given this program as input, is also unable to assign an output.
So humans also can't solve the halting problem, we are just able to recognize that the problem is undecidable.
> What makes you certain there is an algorithmic analog for all human reasoning?
(Maybe) not for ALL human thought but at least all communicatable deductive reasoning can be encoded in formal logic. If I give you an algorithm and ask you to decide if it does halt or does not halt (I give you plenty of time to decide) and then ask you to explain to me your result and convince me that you are correct, you have to put your thoughts into words that I can understand and and the logic of your reasoning has to be sound. And if you can explain to me you could as well encode your though process into an algorithm or a formal logic expression. If you can not, you could not convince me. If you can: now you have your algorithm for deciding the halting problem.