Bjørn Kjos-Hanssen
Moderator
• Member for 11 years, 3 months
• Last seen this week

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-...

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 ...

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 ...

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, ...

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 ...
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 10 votes One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem 6.23. View answer 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 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 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 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 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 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 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 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 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 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 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 6 votes The AUTOMATA workshop series focuses on cellular automata: http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/ View answer 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 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 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 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 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 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 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 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 4 votes An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange. View answer 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 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. ...