Bjørn Kjos-Hanssen
Moderator
  • Member for 11 years, 3 months
  • Last seen this week
Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?
Accepted answer
31 votes

Yes, there are such proofs in computability theory (a.k.a. recursion theory). You can first show that the halting problem (the set $0'$) can be used to compute a set $G\subseteq\mathbb N$ that is 1-...

View answer
Is there algorithmic mathematical analysis?
Accepted answer
18 votes

Check out the Computability and Complexity in Analysis network. Quote: The topics of interest include foundational work on various models and approaches for describing computability and complexity ...

View answer
The TOC Blog Aggregator is Offline
Accepted answer
15 votes

In 2007, Princeton professor Arvind Narayanan created the TOC Blog Aggregator. In 2018, CSTheory.se Moderator Suresh Venkatasubramanian (@SureshVenkat) stepped down from moderating here, but took ...

View answer
Function that is guaranteed to be one-way if one-way functions exist?
Accepted answer
12 votes

Yes, such a function was found by Levin himself, published somewhat recently: The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, ...

View answer
Is there a useful notion of being “approximately computable”
Accepted answer
12 votes

If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very ...

View answer
Is predicting (in the limit) computable sequences as hard as the halting problem?
11 votes

Actually this is easier than solving the halting problem. Let $f:\mathbb N\rightarrow\mathbb N$ be a function that dominates all computable functions, i.e., for all total computable functions $g:\...

View answer
Proof of undecidability not by reduction from the halting problem
10 votes

One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem 6.23.

View answer
Non-comparable natural numbers
Accepted answer
9 votes

When you say "undecidable" I assume you mean it is independent of a theory such as ZFC. There will be statements like $$B(m)>n$$ (for natural numbers $m$, $n$) that are not decided by ZFC, assuming ...

View answer
Is Biological Computation a theme covered by the Theoretical Computer Science?
Accepted answer
8 votes

Yes there is some overlap, for instance the conference Unconventional Computation and Natural Computation (UCNC) covers theoretical computer science topics related to biological computation. From the ...

View answer
On a GI complete class
Accepted answer
8 votes

No, that's not $\mathrm{GI}$-complete unless $\mathrm{GI}\in\textsf{P}$. Indeed, isomorphism of such graphs can be checked in polynomial time. First, note that a bipartite graph is triangle-free. ...

View answer
Can a probabilistic Turing machine solve the halting problem?
8 votes

If the Lebesgue measure of those oracles that compute a set $A\subseteq\mathbb N$ is positive, then $A$ is computable. This goes back to de Leeuw, Moore, Shannon, and Shapiro in 1956 and Sacks in 1963....

View answer
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Accepted answer
7 votes

Chaitin in his 1976 paper Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029. studied sets such that ...

View answer
Is algorithmic information theory still evolving?
7 votes

A modern tweak on algorithmic information theory is algorithmic randomness which was developed intensively in the 2000s (2009-2009) and is still quite active. The most notorious open problem there ...

View answer
Does the physical Church-Turing thesis imply that all physical constants are computable?
Accepted answer
7 votes

Yes, if you somehow had a scheme that allows to compute/measure more and more digits of the fine-structure constant $\alpha$ then $\alpha$ should be Turing computable according to the Church-Turing ...

View answer
Computability Theory prerequisites
Accepted answer
7 votes

Theory of computation and automata theory are not really needed for pure computability theory (but they are a very nice complement to computability theory and certainly help put it in perspective and ...

View answer
Expected Kolmogorov complexity under Kolmogorov complexity distribution
7 votes

If $\alpha$ is the answer to the 1st question then $\alpha=\infty$. Namely, for any $c $ there is an $n $ such that all strings $w $ of length at least $n $ have $K (w) \ge c$. In particular the ...

View answer
Proof refutation: Amateur reviews of ambitious CoRR papers
6 votes

If you make an arXiv trackback you will not be ignored, in the sense that future readers of the ambitious arXiv paper may check the trackbacks. You even get a mild form of peer review for your posts, ...

View answer
Sorting a programs instructions until it works
Accepted answer
6 votes

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$. (Of course, that does not guarantee that you found the correct ...

View answer
Are there any schools with researchers interested in cellular automata?
6 votes

The AUTOMATA workshop series focuses on cellular automata: http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/

View answer
Why colon to denote that a value belongs to a type?
5 votes

Björn, There's probably an earlier reference but for one thing, the colon was used in the Pascal programming language:

View answer
P vs. NP in a logic with a random oracle
5 votes

Yes on Question 1 (assuming ZFC is consistent). You don't need $f$ to be random exactly, any $f$ will do. And for the proof you need to also use the fact that there is an oracle $h$ with NP$^h=$P$^h$.

View answer
Enumerating decidable languages
5 votes

While @LanceFortnow answered the question asked, since the OP mentioned deciders, I'll mention what kind of oracle is needed for that. Jockusch showed that the computable sets are $A$-uniform iff $A$ ...

View answer
Term for a set that is not immune
Accepted answer
4 votes

If a set $A$ is Turing reducible to a set $B$ then we say that $B$ computes $A$. Every noncomputable set $A$ computes an immune set, namely $\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$. (...

View answer
Is the Chi-square divergence a Bregman divergence?
Accepted answer
4 votes

$\chi^2$-divergence is not a Bregman divergence. I'll show it for sample size $n=1$. We would have $$ (x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$ If $y=0$ and $x>0$ this says $$x=f(x)-f(0)-xf'(0),$$ $$1=\...

View answer
Bootstrapping results that really bootstrap
4 votes

Huang's recent proof of $A'$, the Sensitivity Conjecture, involved proving an $A$ known to imply it. See Aaronson's blog: From pioneering work by Gotsman and Linial in 1992, it was known that to ...

View answer
Is there any research on approximation of reals with computable numbers
4 votes

It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and ...

View answer
"Verifiable information": is this a known concept?
4 votes

$K\subseteq\{0,1\}^\omega$ is $\mathsf{R}$-verifiable if and only if $K$ is a $\Pi^0_1$ class (in Cantor space), a concept that has been studied extensively in computability-theory. They are also ...

View answer
Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?
4 votes

An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange.

View answer
Connection between algebraic logic and computational complexity of logics?
Accepted answer
4 votes

The example you gave extends as follows: SAT for arbitrary lattices (meaning, is a given formula satisfiable in some lattice) is polynomial-time decidable SAT for modular lattices is Turing ...

View answer
Program equivalence wherein the programs are known to always halt
4 votes

Consider programs $e_1$, $e_2$ and numbers of time steps $t$. Let $f_i(t)$ be the output of $e_i$ after $t$ steps, and let $f_i(t)$ output a special message like "none" if there's no output yet. ...

View answer