5
There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.
The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary ...
4
You said in a comment:
I am talking to process this encoding, not the tape content.
But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape.
You want to "go through all encoded transitions ...
3
You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state.
However, I would like to warn against interpreting this observation in the wrong way. It is not a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed ...
3
P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.
3
Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.
Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define
$$L_2 = \lbrace b w \mid w \in H\rbrace$$
and
$$L_1 = L_2 \cup \lbrace a \rbrace.$$
Now it is obvious ...
2
The answer is "we don't know without more information" for all 4.
Suppose $f$ is the identity function $f(x) = x$. Then $f \circ g = g \circ f = g$, which is non-computable.
On the other hand, suppose $g$ is a total non-computable function (which is a special case of $g$ being a partial non-computable function), and suppose $f$ is the constant zero ...
2
Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.
2
As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$.
The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$.
Here is the ...
2
Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal initial configuration.
2
Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.
2
$D$ verifies $\langle M \rangle$ is a (deterministic) TM and then builds the configurations graph and checks if the initial configuration of $\epsilon$ is connected to an accept state (there are only finitely many) and returns true if there is and false if there isn't.
The problem here is that, even if you define the TM so that there are only finitely many ...
1
In slightly more detail, what's happening is:
Run the machine on input $s_1$ for one step. If it accepts, list the string.
If the machine didn't halt on the previous step, run the machine on $s_1$ for one more step and then on $s_2$ for a step. As before, if the machine accepts either string, list them and remove them from consideration.
Do the same thing ...
1
A language is Turing-recognizable (or Recursively enumerable) iff there exists a Turing Machine which will enumerate all valid strings of the language.
What you probably miss in the above proof is the fact that $i$ can take any value ... when we say $i$ steps, we can mean $10$, $100$, $100000$, $\infty$ steps.
Basically $i$ is an index that indicates the ...
1
No pushdown automaton can recognize this language, because the language is not context-free. This can be shown using the pumping lemma for context-free languages or Parikh's theorem. The latter gives a particularly straightforward proof: the language is not context-free because $2^n$ cannot be written as a finite union of linear functions.
The language is ...
1
Actually this language is not a CFL.
And here is a proof:
Let's take string $w: a^mb^{2^m}$ where $m$ is constant guaranteed by pumping lemma for CFLs.
Then $a^{m+k_1}b^{2^m+k_2} \in L$ where $1\le k_1,k_2<m$
(cases invloving either $k_1 = 0$ or $k_2=0$ are easier.)
Now, that suggests that,
$2^{m+k_1} = 2^m + k_2$ (by defination of $L$)
$\therefore ...
1
Let HALT be the following version of the halting problem: Given a Turing machine $T$, determine whether it halts on the empty input.
Here is a computable reduction from HALT to $L_{all}$: Given a Turing machine $T$, construct a Turing machine $T'$ which erases its input and then transfers control to $T$. You can check that $T \in \mathrm{HALT}$ iff $T' \in ...
1
Maybe you can write sth like "Σ\2 → x, R" on the transition. But as Yuval Filmus mentioned, the notations always depend on the lecturer.
1
You could write $\neq 2 \to x,R$, but you might have to explain somewhere that by that you mean that the transition is taken as long as the symbol read is not $2$.
More generally, you can use whatever notation you want as long as you explain it and it's unambiguous.
This is the answer of a practical mathematician. Your professor could have different ideas.
1
A Turing machine diagram is a form of communication. Its goal is to describe a Turing machine — usually defined as a tuple with a specific format — in a form which is easier to grasp. As such, you can use whatever shortcut you want, as long as everybody understands what you mean. This might entail your explaining some non-standard notation which ...
Only top voted, non community-wiki answers of a minimum length are eligible
