Enumerator for Word and Halting Problem

Question

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

Steven · Answer

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$.

Enumerator for Word and Halting Problem

One Answer

Add your own answers!

Ask a Question