Halting problem vs Universal Language

Question

Wikipedia defines halting set as follows:

$H = \{(i, x) |$ program $i$ halts when run on input $x\}$

Ullman defines universal language as follows

$U = \{(M, w) |$ Turing machine $M$ accepts $w\}$

This link says:

The universal TM, $U$, is a TM which takes as input an encoded machine/string pair, $(M,w)$, and performs the actions of $M$ running with input string $w$. The most important achievement is to simulate the accepting (i.e., halting) behavior of M. That is we want:

$M$ halts on $w$ if and only if $U$ halts on $E(M,w)$
or, in notational terms,
$M↓w$ if and only if $U↓E(M,w)$

Note that $E()$ is encoding function. Also I feel above defines universal language somewhat different than what Ullman defines. While defining universal TM, Ullman says "$M$ accepts on $w$", whereas above link says "$U$ halts on $E(M,w)$". Its accept vs halt which is I am trying to point out. I feel TM can halt with or without accepting. So I feel the definitions of universal language differs in both sources. Q1. Right?

Thats why the link says:

HALT $= \{ x ∈ \{c,1\}^*: x = E(M,w)$ where $M↓w \}$
HALT is precisely the language accepted by the Universal Turing Machine, U:
$M↓w$ if and only if $U↓E(M,w)$

where $↓$ seems to be symbol indicating "halts"

But Ullman says:

One often hears of the halting problem for TMs as a problem similar to $L_u$ - one that is RE but not recursive. In fact, the original TM of A. M. Turing accepted by halting, not by final state. We could define H(M) for TM M to be the set of the inputs $w$ such that it halts given input $w$, regardless of whether or not $M$ accepts $w$. Then, the halting problem is the set of pairs $(M,w)$ such that $w$ is in $H(M)$

By this, I feel Ullman disagrees that halting language is what is accepted by Universal TM.

The link also says:

In particular, the universal TM accepts HALT, but no TM can decide HALT.

If I get it correct, I believe "universal TM accepts HALT" means Universal UTM can simulate HTM (accepting TM and w as input) which checks whether input TM halts on input w. Q2. Am I right with this? Q3. But then that does not mean L(UTM) = L(HTM) as said by the same link in fourth quote. Right?

Q4. Can you summarise halting problem vs universal language? I feel the link is somewhat incorrect and Ullman is correct. I believe:

• Halting language L(HTM) = {(TM,w) | TM halts on w with or without accepting}

• Universal language L(UTM) = {(TM,w) | TM accepts w by halting in final state}

• From above definitions, Halting language is not same as Universal language

• Universal language can simulate Halting language as follows: (HTM,(TM,w)) | HTM accepts (TM,w) by halting in final state when TM halts on w with or without accepting w

Am I correct with above summary understanding?

Answer 1

So first Q1:

At first the definitions of universal language and the universal machine.

The universal language is defined as you mentioned in the question:

$$ U= \{(M,w)\:|\:\text( TM\:M\:accepts\:w)\} $$

The Universal Turing Machine on the other hand is defined as follows:

A machine, which can simulate an arbitrary TM on arbitrary input. Or you can say: It's a TM U, which you can give a random other TM M and an input w. The Universal TM then simulates the given TM M on that input w.

So the Universal Turing Machine accepts, if and only if the TM M accepts w (because it simulates M on w). It rejects, if and only if, the TM M rejects w. It halts, if and only if the TM M is halting on w (because it simulates M on w). So the Universal Turing Machine accepts the above defined Universal Language.

Now to the question: The definition of the link is a little bit misleading. The Universal TM doesn't accept HALT on default, but you can modify the Universal Turing Machine in a simple way to accept HALT: The reject states are replaced by accept states. The now modified UTM (let's call it U') is accepting HALT. Because now it always accepts, if the machine M is accepting or rejecting the input w, without getting stuck in a loop: U' is accepting, if M is halting on w.

Then Q2:

A "TM M is accepting a language L" means, that it definitely halts on w $\in$ L, but does not mean it halts on w $\notin$ L (it can loop forever). So that means, if the U' is accepting HALT, it holds for sure, only if $(M,w) \in HALT$. If $(M,w) \notin HALT$, the universal TM can halt or can loop forever. So it isn't deciding HALT, it's just accepting HALT.

(Actually it's the slightly modified Universal TM, which is accepting HALT as mentioned in answer Q1.)

Q3:

If you mean the Universal Language with L(UTM) and the halting language with L(HTM), then yes L(UTM) $\neq$ L(HTM).

Q4:

First three points you made are correct.

In the last point you have to be more exact: The (modified) UTM can accept the Halting Language, but cannot decide it. So you can check, whether M halts on w, but it may loop forever.

Answer 2

So I feel the definitions of universal language differs in both sources. Q1. Right?

You quoted Ullman's definition for Universal language but didn't quoted the other source definition of universal language. The other source defined universal Turing machine which is not language. So the answer to your first question is that no you aren't right since the second source didn't have defined Universal language.

I believe "universal TM accepts HALT" means Universal UTM can simulate HTM (accepting TM and w as input) which checks whether input TM halts on input w. Q2. Am I right with this?

If by HTM you mean Halting Turing machine $H$ that halts on its input string $w$, then your statement is correct because if you have a UTM (universal Turing machine) $U$, you can give $H$ and $w$ as its input and simulate $H$ behavior using $U$. By definition of the link, you give $H$ and $w$ as $E(H,w)$ to a universal Turing machine. Note that this Universal Turing machine can only accept whenever $H$ really halts on $w$ but it can't reject when $H$ stuck in infinite loop. So It can't decide $E(H,w)$ which means $U$ can just understand accept but not reject (And there is no TM which can understand when $H$ doesn't halt on $w$).

Q3. But then that does not mean L(UTM) = L(HTM) as said by the same link in fourth quote. Right?

If by $L(UTM)$ and $L(HTM)$ you mean the languages you gave above in the summary part. No they aren't the same.

• Universal language can simulate Halting language as follows: (HTM,(TM,w)) | HTM accepts (TM,w) by halting in final state when TM halts on w with or without accepting w

Am I correct with above summary understanding?

Well, I don't think language can simulate each other. statement you can give about language is that one is subset of the other one that is $L(UTM)\subset L(HTM)$.