Tag Info

4

Not really, unless you include TMs in some way or another in the "situation". Any infinite loop in an NFA must constitute only of $\epsilon$ transitions (since the input is finite, if the loop would have "eaten up" some letters, it must also be finite). As you already know, its pretty easy to get rid of those epsilon transitions, so after ...

2

If the Turing machine is allowed to update each cell twice (or even once, see Hendrik Jan's comment), then you can use the following strategy to simulate an arbitrary Turing machine $T$ using a fragile Turing machine $T'$. For each step of $T$, the contents of the tape of $T$ will appear in some part of the tape of $T'$, with the head position highlighted. ...

1

Design a Turing machine $T$ that takes as an input a word with an unique occurrence of the "@" symbol and shifts all symbols after "@" one position to their left (thus overwriting "@" and replacing the last symbol of the word with the blank symbol). This can be done by finding the end of the input word, setting the machine state ...

1

The third language defines a constant Upper bound for the calculation steps of the machine. There is no constant upper bound on the number of steps of $M$ in $L_3$. $L_3$ is the language of all machines that halt on at least one word $w$ while performing less steps than the length of $w$. The word $w$ is not fixed, all that is needed to $M$ to be in $L_3$ ...

1

The tape contains whatever the Turing machine wants it to. There's no rule that says it has to have certain contents. It must have a finite number of symbols, and all the spaces outside of a finite region must be blank.

1

I think that if $H$ has $D$ as a subroutine, when $D$ is running, $D$ could terminate in a halting state, making the whole of $H$ terminate without exiting the subroutine. I think this is the core of your argument - stated again here: $D$ can be built so that, if needed, it directly terminates in such necessary state without passing through the rest of $H$’...

Only top voted, non community-wiki answers of a minimum length are eligible