Note that all the major programming languages in use
undecidable: there is no way to predict, in general, whether
any given program will ever halt. Programmers don't "solve"
that problem by limiting the expressive power of the languages.
Instead, what they do is to define intermediate levels so that
the mapping from one level to the next is manageable with our
limited ability and resources for reasoning about complexity.
Yes and intermediate steps (procedures,
functions, classes, structures…) are each expressing portions of the complete
problem. There simply has to be a noncyclic spiral over the duration of the
program for each action that focuses ever more tightly onto the solution. That
is relatively easy to do.
And since Lisp, we’ve known how to
represent the programs to the programs themselves. But lisp wasn’t a
good enough vehicle for natural language at the time. Too simple in the face
of huge conceptual complexity. But the old days are transitioning into
tomorrow and we can already toss adequate computing power at any problems that
we can approximate iteratively.