Search Results

Although the other answers point out correctly that the exact value of $\text{BB}(n)$ is independent of ZF for large enough and even moderately sized values of $n$, nevertheless I should like to point …

Here is one way of interpreting your question. In my joint paper: Joel David Hamkins and Alexei Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Form …

As you noticed in your question, for any particular value of $n$, there is a constructive algorithm that solves the halting problem for instances of size at most $n$. Since for a particular value of $ …

It's simple. If the halting problem is undecidable, then PA is not complete, since otherwise, you could solve the halting problem by searching for proofs in PA. And the same argument works for any sou …

Peter Koepke and Martin Koerwien developed the theory of sets of ordinals as a foundation of mathematics, showing senses in which it is equivalent to ZFC as a foundation. Peter Koeopke and Martin Koe …

Your building blocks are known as the atoms in the Boolean algebra or field of sets generated by the $A_i$. Each building block will consist of points that have the same pattern of answers for members …

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 …

Allow me to mention that since the players in effect adopt the roles of the quantifiers $\forall$ and $\exists$, as Bob has a winning strategy just in case for every move for Alice, there is a reply b …

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 …

The quotient of one language $L$ by another $R$ is the set of strings $x$ such that $xy\in L$ for some $y\in R$. If both $L$ and $R$ are computably enumerable (what you call RE), then the quotient i …

The answer is that you have to apply another primitive recursive function after the $\mu$ operator. Specifically, the Kleene normal form is that every recursive function $f$ has the form $f(n)=U(\mu x …

One answer to your question is that it depends on the underlying model of computability you are using. Specifically, although this is a little different than your set-up, but for one of the standard …

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 …

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 …

Of course there can be no "worst" algorithm, since for any algorithm taking $p(n)$ steps on input of size $n$, we can easily design another algorithm taking $2^{p(n)}$ steps, which will be worse by th …