4
Suppose you have two mutually recursive maps $f, g :
\mathbb{N} \to \mathbb{N}$ defined by
\begin{align*}
f(n) &= \Phi(f, g, n), \\
g(n) &= \Psi(f, g, n)
\end{align*}
We may replace this with a single recursive map $h : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$, where $h(n) = (f(n), g(n))$, so that $f(n) = \pi_1(h(n))$, $g(n) = \pi_2(h(n))$. ...
4
Let $A \subseteq \mathbb{N}$ be an arbitrary subset containing $0$. Define $L_1 = \{0^n 1 : n \in A\}$ and $L_2 = \{0^n : n \in \mathbb{N}\}$. Then $A$ reduces to $L_1L_2$, but $L_2L_1 = \{0^n1 : n \in \mathbb{N}\}$.
3
A decision algorithm is required to behave as an "observationally pure" function. In other words, its externally observable behavior (for someone who can run it on inputs of their choosing and observe what it outputs) must be consistent with it being a pure function.
Presumably, unless you specify otherwise, any normal reader of your definition of ...
2
Every language reduces to itself. Take $L_1 = L_2$ to be any recursively enumerable language which isn't recursive.
2
Either the instance has no solutions or you can obtain infinitely many solutions by repeating the same sequence of selected pairs of words multiple times.
More precisely, using the definitions from Wikipedia, let a solution be:
$$
\alpha_{i_1} \alpha_{i_2} \dots \alpha_{i_K} = \beta{i_1} \beta{i_2} \dots \beta{i_K},
$$
then the following is also a solution:
$...
2
Turing machines can be encoded as integers in various ways. With respect to any such encoding, we define $\mathcal{H}$ as the set of integers $n$ such that the Turing machine encoded by $n$ halts on the empty input.
The encoding cannot be completely arbitrary. For example, you can design such an artificial encoding in which the parity of the encoding is its ...
1
You can recognize $\{a^nb^n\}$ with just a counter (which is incremented by an $a$ and decremented by a $b$). No additional stack is needed. (If you used a stack, it would only contain $a$s; in general a counter is functionally equivalent to a stack whose alphabet consists of only one symbol.)
The answer to the question you link to provides an example of a ...
1
Take $l(\bar{a}, x, y) = h(\bar{a},y)$.
More precisely, writing $\pi_i$ for the $i$-th projection from $\mathbb{N}^{p+2}$ to $\mathbb{N}$, we see that $l$ is the composition of $h$ and projections, as follows:
$$
l(a_1, \ldots, a_p, x, y) =
h(\pi_1(a_1, \ldots, a_p, x, y), \ldots,
\pi_p(a_1, \ldots, a_p, x, y),
\pi_{p+2}(a_1, \ldots, a_p, x, y))
$$
1
The set $\Sigma^*$ consists of all words over $\Sigma$.
A language over $\Sigma$ is not a word over $\Sigma$. Hence no language is a member of $\Sigma^*$, and no set of languages is a subset of $\Sigma^*$.
1
Let COF consist of all Turing machines which halt on all but finitely many inputs. It is known that COF is $\Sigma_3$-complete, see here for example.
Given a machine $M$, whose inputs we identify with $\mathbb{N}$, we can construct another machine $M'$, defined as follows:
If the input is not of the form $1^{n_1} 0 1^{n_2} 0 \cdots 0 1^{n_m}$ for some ...
1
There will be no contradiction, since $D$ doesn't run in time $n^{1.4}$. In fact, what the proof of the time hierarchy theorem shows is that no equivalent Turing machine can run in time $n^{1.4}$, precisely because this will result in a contradiction. In other words, the language computed by $D$ lies outside of $\mathrm{DTIME}(n^{1.4})$. On the other hand, $...
1
"Computational resource" is a bit of an open-ended notion, but it always signifies a capacity for a program to use, control, or inspect something that is external to the program itself.
According to this understanding your suggestions are not computational resources. They are closer to something like "observations about the behavior of the ...
1
No. However, its true that $L_2$ is at least as hard as $L_1$. The opposite isn't true: take for example $L_2$ being the halting problem, and $L_1=\emptyset$.
1
Subsets of recursive languages aren't always recursive or recursively enumerable. The simplest example is the language of all strings: it is clearly recursive (even regular), and all languages are its subsets including those not in $RE$.
To solve this question, consider this: how many subsets does an infinite language $L$ have? What does that imply regarding ...
1
The correct answer is no. 3.
Suppose $A \in \text{NP}$ and $A \notin \text{co-NP}$. Clearly this shows $\text{NP} \neq \text{coNP}$, but that's not a possible choice for this question.
Observe that complement of the machine output can be trivially implemented in a deterministic polynomial machine. That is to say, $\text{P} = \text{co-P}$. Thus, if $\text{P} =...
1
As $\mathrm{SAT}$ is $\mathrm{NP}$-complete, we know that there is a polytime reduction from our language $L$ to $\mathrm{SAT}$. However, this reduction can involve a polynomial blowup of the input size. This means that an input $w$ to $L$ could be mapped to a formula $\phi_w$ such that $|\phi_w| \approx |w|^k$ for some constant $k$.
Running our hypothetical ...
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