Considering that people were having typical days of programming before complexity theory existed, of course it's not required. I don't know of anybody who seriously claims that it is required.
I suggest you read that more closely. There was no theory laid out until the late 60's, and "complexity theory" was not a field until the 70's. On the other hand, there is a long list of programming languages invented in the 50's.
Did I say anything about efficiency? Computability itself is a topic within computational complexity, as (in many ways) it's one of the "hardest" rungs of the complexity ladder.
I'm sorry, but you're wrong. Complexity theory is by definition the subfield of computer science that studies the efficiency of algorithms, or the inability for algorithms to meet certain efficiency requirements.
This is my field of research, and I assure you computability theory is not a subset of it.
No - complexity theory deals with the "hardness" of problems not of algorithms, and yes, then the bounds on what algorithms we can write to solve them.
By that metric (and even by your own argument "the inability for algorithms"), the undecidability of the halting problem definitely fits within the complexity definition.
That is what I understood you as saying. I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid.
In any case, it's clear from your appeal-to-wikipedia that this conversation is over.
