Skip to main content
Theoretical Computer Science
Bjørn Kjos-Hanssen's user avatar
Bjørn Kjos-Hanssen's user avatar
Bjørn Kjos-Hanssen's user avatar
Bjørn Kjos-Hanssen
  • Member for 13 years, 10 months
  • Last seen more than a week ago
Profile Activity

71 Answers

Score Activity Newest
33 votes
Accepted

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

18 votes
Accepted

Is there algorithmic mathematical analysis?

15 votes
Accepted

The TOC Blog Aggregator is Offline

12 votes
Accepted

Is there a useful notion of being “approximately computable”

12 votes
Accepted

Function that is guaranteed to be one-way if one-way functions exist?

11 votes

Is predicting (in the limit) computable sequences as hard as the halting problem?

10 votes

Proof of undecidability not by reduction from the halting problem

9 votes

Can a probabilistic Turing machine solve the halting problem?

9 votes
Accepted

Non-comparable natural numbers

8 votes
Accepted

On a GI complete class

8 votes
Accepted

Is Biological Computation a theme covered by the Theoretical Computer Science?

8 votes
Accepted

Does the physical Church-Turing thesis imply that all physical constants are computable?

7 votes
Accepted

Computability Theory prerequisites

7 votes

Expected Kolmogorov complexity under Kolmogorov complexity distribution

7 votes
Accepted

Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

7 votes

Is algorithmic information theory still evolving?

6 votes

Proof refutation: Amateur reviews of ambitious CoRR papers

6 votes
Accepted

Sorting a programs instructions until it works

6 votes

Are there any schools with researchers interested in cellular automata?

5 votes

P vs. NP in a logic with a random oracle

5 votes

Enumerating decidable languages

5 votes

Why colon to denote that a value belongs to a type?

4 votes

Bootstrapping results that really bootstrap

4 votes
Accepted

Is the Chi-square divergence a Bregman divergence?

4 votes
Accepted

Term for a set that is not immune

4 votes

Is there any research on approximation of reals with computable numbers

4 votes

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

4 votes

"Verifiable information": is this a known concept?

4 votes
Accepted

Connection between algebraic logic and computational complexity of logics?

4 votes

Program equivalence wherein the programs are known to always halt

1
2 3