But even if it were a more powerful model, it would still be subject to an analogous halting problem. This is well-trodden ground. It is a misunderstanding to believe that the halting problem is fundamentally tied to the exact power or nature of Turing Machines.
I tried to reason about it in different ways. Such as, for case 1, considering Z(Z) halts. I don't think it's unreasonable to say that H(Z,Z) could in fact return true. It could read the code for Z, determine that Z(Z) will loop since H(Z,Z) would return false, return true, and then Z(Z) would halt since H(Z,Z) returned true. No immediate contradiction.
Problem is that doesn't completely eliminate the contradiction, it just introduces another one. Even if Z(Z) halts and H(Z,Z) returns false, you could argue backwards and say that the only way for Z(Z) to halt is if H(Z,Z) returns true, but H(Z,Z) can't return two different results.
Part of me still doesn't like the negator program. Too many contradictions. Apparently there are constructive proofs for the halting problem too, which I don't understand yet, so the rabbit hole continues.
Thanks again for engaging.
This doesn't make sense. You said in the same case both that "Z(Z) halts" and "Z(Z) will loop" and then "Z(Z) would halt". So there is a contradiction here.
One assumption that you may not realize without the necessary background is that (a) "Z" is fixed in any particular case, we don't consider counterfactual "Z"; and similarly (b) "Z(Z)" must either always halt or always not halt, by the relevant definition of "program".
I may have found what I've been looking for in a related topic called Oracle machines for the halting problem. Part of its definition is that it can't solve problem for machines equivalent to itself, which, I believe, would exclude Z-type programs from the domain.
To put my plea into some formal jargon, "Just because the halting problem is undecidable doesn't mean oracles Turing machines for the halting problem don't exist." Kind of a simple and obvious point in hindsight, but I'm happy with it.
To me, your question is like asking this: Do all the programs that we humans ask computers to compute come from a finite program? Is life itself powered by a finite program?
A program which keeps growing can make use of all the code it has seen before, all the results it has seen from running code previously. Although any of its inputs are finite strings, there are no theoretical limitations regarding the source of the inputs it can receive. They come from outside.
The core idea of the undecidability of the halting problem is that we can construct a machine M that can ask the halting machine for a bit, flip the bit, give it back to the same static halting machine code, thus forcing it to produce the wrong bit.
Any human in that situation would change their understanding of the situation, and we would tend to afford them a chance to change their answer based on their new understanding. Being able to adjust execution strategy after seeing new information is core to human life. Why do we neglect to provide computers opportunities which are available to all humans?
A somewhat trivial reply to Turing's original negator machine M would be to emit a new version of the halting code which checks for the exact code given by M and then returns the opposite of what was returned when M calls out to H. Then, in the argument, we would need to address the possibility that the H machine called out in M to may provide a different answer when we pass it all back through H again. The argument wouldn't work as-is if we afforded H the ability to respond to the situation.
What would the statement be? "It is not possible, given the information the halting code just received, it could change its answer response to the contradiction of its previous answer." A child can figure out this simple trick - we all understand why it's a trick - why do we not let a computer the same opportunity in our theory?
> So long as you have enough memory, ...
True enough. My point was in fact that if the inputs our machine receives are all needed, we would run out of memory eventually.