Search Results

Your second question is a little ambiguous, because it admits the following cheating affirmative answer, which is probably not what you intend. Namely, every NFA with n states is equivalent to a DFA …

I think that the blow-up in time can be much worse than you describe, depending on the specific computational models that are used. For example, consider the function that accepts an input string $w$ …

Both statements are true. For statement (1), consider any fixed program $p$, to be run on input $0$. If $p$ actually halts on that input, then this will be provable in PA. If it doesn't, then the a …

Let $TA$ be the theory of true arithmetic, that is, the set of all truths of the usual standard model of arithmetic $\langle\mathbb{N},+,\cdot,0,1,<\rangle$. It is a theorem of ZFC that TA is consiste …

I'm not sure what you mean by $\oplus$, but here is a counterexample. Let each $\phi_i(\vec x)$ be a tautology. So $S(\phi_i)=2$. But $\phi_1\oplus\cdots\phi_x$ is also trivial (depending on what you …

Let's assume that Mark's description of the problem in the comments is correct, so that we have a fixed polynomial $P$, and the decision problem is: given $l$ and $n$, such that $l\lt \log(n)$, decide …

The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture …

The general abstract setting for the issue driving your question is the notion of reduction of equivalence relations. The idea of this is that one equivalence relation $E$ reduces to another $F$ with …

In general, there will be no such fixed points, even when the range of $f$ consists of programs for total computable functions. The reason is that we can easily compute a list of programs for distinct …

Yes, the class NP $\cap$ coNP is closed under symmetric difference. To see this, suppose that $A$ and $B$ are both in NP $\cap$ coNP. This means that the truth of $a\in A$ can be verified in polynomia …

Let $b_k$ be the assertion that the busy beaver function at $k$ has the value that it actually has, that is, the value it has in the standard natural numbers of the meta-theory. We know that not all o …

Your question is about many things, but let me give an answer focused on just one interesting issue, the question of determining how long a program will run. The busy beaver function exactly measure …

The principal motivation for the Blum Shub Smale model of computability was precisely the kind of concern you raise in your question. In particular, the BSS machines provide a numerical model of compu …

The answer seems to be no, this is not decidable. You seem to have a concept in mind of what it means for a program $p$ to be UTP, and it involves the idea that pieces of any given computation histor …

Since there are computable total functions that are not primitive recursive, one cannot make the two notions of time complexity coincide. If we add any primitive recursive function as an initial funct …