We can probably agree a complete, bounded, definition is not possible. I agree with your description. But it still leaves room for debate.
I've been faced with computational problems when writing HTML many times before; The HTML <link> tag is used to define the relationship between two documents. They are needed for many things; to have the browser display an icon on the address bar; to define what device a document should be displayed on (handheld, tty, print, braille, aural, ...), to define content-types and charsets, to include stylesheets.
HTML sole purpose in life is to provide content with new and correct semantics in the context of the parser used to interpret it. In this context how can anyone think of it as a programming language? However, tags like <div> and <span> take the markup to a new higher level in which it is possible to define our own new semantic tokens and attribute them to the content. The decision to do so, or not, coupled with how and where it should be done, is largely based on our knowledge of the browser rendering engine (the HTML "compiler") and the need or not alter how the content is to be rendered. This is too solving a computational problem.
For this reason I'll end the way I started; We can probably agree a complete, bounded, definition of what is a Programming Language is not possible anymore. It becomes easier today to say what is not a programming language, than to say what it is.
I do agree HTML is not a programming language. But that is mostly based on my own (at the present time and probably skewed) view of what one should be. And that always includes a compiler or interpreter and the ability to perform the following operation x + y. Other may not agree. And they will be as right.