4
The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general:
Deciding ...
3
The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his ...
2
Skelet has 43 holdouts (those with type = ----).
At least No. 827123 (the very first in the lists) is still open, afaik.
My "feeling" is that all but 6 (no idea, which!) have been shown to be infinite.
Good luck!
http://skelet.ludost.net/bb/nreg.html
No info on actual holdouts, but state-of-the-art in several aspects:
https://www.scottaaronson.com/...
2
(For the below, I referred extensively to this github repo as well as private communication with @aozgaa)
Languages can be represented as infinite-length bitstrings (ILB). We will use the two interchangeably. We will also represent strings meant to be inputs to TMs as integers, where a 1 bit in position $w$ in an ILB $A$ means that the $w$th string in $\...
2
Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (...
2
First observe that any $S \subseteq \{0,1\}^\mathbb{N}$ described by a $\Delta^0_1$-formula is clopen (open and closed subset), where we topologize with the product topology. Indeed, the subbasic sets of the form $B_{i,k} = \{x \in \{0,1\}^\mathbb{N} \mid x(i) = k\}$ are clopen by definition, and then complements (negation), finite unions (disjunction and ...
1
When $n$ is large, $T(n-\sqrt{n})$ is much larger than $T(\sqrt{n})$. Therefore, roughly speaking,
$$ T(n) \approx T(n-\sqrt{n}) + \Theta(n). $$
Now let us imagine extending $T$ to all inputs, and suppose that it was differentiable. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and consequently
$$ T'(n) \approx \Theta(\sqrt{n}) \Longrightarrow T(n) = \...
1
Your function produces the sequence A109128, that is
$$
\mathit{recurser}(i,j) = 2\binom{i+j}{i} - 1.
$$
You can prove this by induction.
How I found out: I computed the first few values, and searched the OEIS.
1
The context-free languages are not closed under complement. For example, $\overline{\{a^nb^nc^n : n \geq 0\}}$ is context-free, but its complement isn't.
1
The first part of the disjunction is for stating that the next "state/m-configuration" of the machine is the one established in $Inst(q_i, S_j, S_k, L, q_l)$ (in case z takes as value the next cell of y', i.e., y), the second part of the disjunct is used to say that the part of the tape not scanned by the machine preserves its value.
1
Suppose a computable mapping reduction $t: \Sigma^* \to \Sigma^*$
from $EQ_{TM}$ to $\overline{EQ_{TM}}$ exists.
We want to create TM's $A,B$ such that for $\langle A', B' \rangle = t(\langle A,B \rangle)$, we have
\begin{align}
L(A) &= L(A') \\
L(B) &= L(B')
\end{align}
We will nest the recursion theorem to accomplish this goal. Our "...
1
An effective algorithm could be the following:
Replace each polynomial by their quotient with their GCD with their own derivative. This is just to make possible multiple roots simple, in case the inputs had them.
Replace the polynomials $P$ and $Q$ by polynomials by the resultant $R(t)$ of $P(x)$ and $x^{\deg(P)}P(t/x)$ and the resultant $S(t)$ of $Q(x)$ ...
Only top voted, non community-wiki answers of a minimum length are eligible
