1
$\begingroup$

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be. And let the Wordproblem be $ L = \{ \langle M, w \rangle | M \space is \space TM \space and \space w \in L(M) \} $ and Halting Problem $ L = \{ \langle M, w \rangle | M \space is \space TM \space and \space M \space halts \space on \space w\} $

Ok for word problem: since there exists a sequence of $M_i$ I would start with $M_1$ and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all $w_i$ to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on for a sequence of computable words $w_1, w_2,.. \in \Sigma^* $ Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while... Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?

Greets,

Felix

Improve this question
$\endgroup$
  • $\begingroup$ Did you check a proof? THe proof I've seen is pretty constructive: cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/… $\endgroup$ – Dmitry Jul 19 '20 at 23:12
  • $\begingroup$ yeah I spent more time understanding the proof as well. So finding the grammar comes more down to finding the TM and what the TM, since once we have the TM we just use construction rules. Finding a TM seems more intuitve. $\endgroup$ – FelixOuttaSpace Jul 20 '20 at 7:43
  • $\begingroup$ What's the word problem? Can you write or add a reference to a formal definition? $\endgroup$ – Steven Jul 20 '20 at 21:48
  • $\begingroup$ added the definition. sorry didn´t found this one over google and wikipedia linked me to unprecise english sites from german definition. what is the acurate name for it? $\endgroup$ – FelixOuttaSpace Jul 20 '20 at 22:25
  • $\begingroup$ So $w$ is just some fixed word, given as a parameter of the problem? In that case the same strategy in my answer also works for the word problem. (Just simulate $T$ with input $w$) $\endgroup$ – Steven Jul 20 '20 at 22:27
1
$\begingroup$

Let $\Sigma = \{0, 1\}$. Clearly $\Sigma^*$ is enumerable. For the word problem you can proceed as follows.

  • For each pair $(i,j) \in \mathbb{N}_+^2$ in dovetail fashion:
    • Let $w_i$ be the $i$-th word in $\Sigma^*$.
    • Check whether $w_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
    • Simulate the Turing machine $T$ with input $w$ for at most $j$ steps.
    • If $T$ halts at the end of the $j$-th step, output $T$.

For the Halting problem you can do as follows:

  • For each pair $(i, j, k) \in \mathbb{N}_+^3$ in dovetail fashion:
    • Let $w_i$ be the $i$-th word in $\Sigma^*$.
    • Let $w_j$ be the $j$-th word in $\Sigma^*$.
    • Check whether $w_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
    • Simulate the Turing machine $T$ with input $w_j$ for at most $k$ steps.
    • If $T$ halts at the end of the $k$-th step, output $\langle T, w_j \rangle$.
Improve this answer
$\endgroup$
  • $\begingroup$ okay seems legit though for constructing an enumerator for the halting problem wouldn´t you have to run $M_i = w_i$ over all $w_1,w_2,... \in \Sigma^*$? $\endgroup$ – FelixOuttaSpace Jul 20 '20 at 22:33
  • $\begingroup$ Depends on the exact definition of the halting problem. I'm enumerating the set of Turing machines $T$ such that $T$ eventually halts on empty input. Are you interested in all the pairs $\langle T, w \rangle$ such that $T$ halts on $w$ instead? $\endgroup$ – Steven Jul 20 '20 at 22:36
  • $\begingroup$ yes I was thinking about pairs of $ \langle M, w \rangle $ didn´t consider details in definition since I thought these problems are universally well known though it really makes a difference. What do you ecactly mean by $N_+$ what is the plus required for? $\endgroup$ – FelixOuttaSpace Jul 20 '20 at 22:42
  • $\begingroup$ also regarding any pair $(i,j) \in \mathbb{N}_+^2$ wouldn´t you have to define in which order the TM´s $M_i$ are being simulated. Maybe we could use some kind of diagonalisation argument for this one and define third axes for all pairs over $w_1, w_2,...$ $\endgroup$ – FelixOuttaSpace Jul 20 '20 at 22:48
  • 1
    $\begingroup$ I'm looking at the pairs (and triples) in dovetail fashion. So first $(1,1)$, then all the pairs that sum to $3$, i.e., $(1,2)$ and $(2,1)$, then all the pairs that sum to $4$, i.e., $(1,3)$, $(2,2)$, $(3,1)$, etc. See e.g., this figure which is about enumeration rationals but uses the same idea. $\endgroup$ – Steven Jul 21 '20 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.