Here's quite a good general answer of when and how to hyphenate. This makes me believe, that Turing-complete is correct, even though most people are not writing it this way.
However, Turing-completeness seems to me to be an extension of Turing-complete—Turing-complete + ness. It's not the completeness of Mr. Turing.
Do I need to get my understanding supplemented here? How?
EDIT:
The answers to To hyphenate or not? don't answer this question.
Is the hyphen in Turing-completeness considered wrong, or not exactly wrong but totally unnecessary? It's hard to put into words, but this compound word has a flair that distinguishes it from a mere compound word that combines two nouns, and I feel urged to express this with a hyphen, just like in the compound word Turing-complete.
6.40: Where the compound adjective follows the noun it modifies, there is usually little to no risk of ambiguity or hesitation, and the hyphen may be safely omitted. [There are, of course, exceptions to this, as in "her reply was thought-provoking."] ...
– Edwin Ashworth May 11 '18 at 13:59