0
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Hi, can you please properly define (in mathematical formula) the language you want to prove this for? $\endgroup$
    – nir shahar
    Dec 9, 2021 at 15:35
  • $\begingroup$ @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. $\endgroup$
    – Anon21
    Dec 9, 2021 at 17:54
  • 1
    $\begingroup$ 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 $\endgroup$
    – nir shahar
    Dec 9, 2021 at 20:52
  • $\begingroup$ And even more confusing is that some of the infinite strings it can output, but some others no TM can ever output. $\endgroup$
    – nir shahar
    Dec 9, 2021 at 20:52
  • $\begingroup$ @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? $\endgroup$
    – Anon21
    Dec 9, 2021 at 21:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.