# Is the set of all halting programs for all universal Turing machines recursively enumerable?

I understand that one can use dovetailing to recursively enumerate the domain of a UTM.

However, I am trying to recursively enumerate the domain of all possible UTM.

My starting point was to use a similar algorithm to dovetailing, but then I realize that I do not know the set of all universal Turing machines.

Proving that an arbitrary two-input Turing machine is a UTM : UTM(TM, d) for all TM and all d; one has to try it out for all possible inputs and confirm that it does, right? And this is non-decidable.

So I can't recursively enumerate all halting programs for all universal Turing machines. I must first pick a specific program known to be a UTM before I can do it? Is my argument sound?

edit: I suppose the question reduces to; given an arbitrary language or Turing machine, prove that it is Turing complete or a universal Turing machine, or is the question undecidable?

I suspect that it is undecidable.

• Hi, can you please properly define (in mathematical formula) the language you want to prove this for? Dec 9, 2021 at 15:35
• @nirshahar Well, I am trying to hit a general result, so if I specify a language, I break the generality. But we can do it as follows: Assume a finite alphabet Z. The words of this alphabet are W. Then a one-input TM is a function of W to W, and a two-input DM is a function of W x W to W. Finally, an encoder function <.> is a map from TM to W. Then if DM(<TM>,w>)=TM(w) for all words, then DM is a UTM. With this I can dovetail the words and enumerate the domain of a UTM. But since I can't know if a given word w = <DM> is or isn't a UTM, I can't dovetail the words over only UTMs. Dec 9, 2021 at 17:54
• FYI, a TM is not a function from words to words. TMs can get stuck in an infinite loop and not output anything. Or maybe output an infinitely long string Dec 9, 2021 at 20:52
• And even more confusing is that some of the infinite strings it can output, but some others no TM can ever output. Dec 9, 2021 at 20:52
• @nirshahar Well it has to be a function from a set to another set... what are the those sets? I suppose technically TM is a function from words to Dom(TM); the later also a set of (carefully chosen) words? Dec 9, 2021 at 21:36