All Questions
Tagged with computability-theory it.information-theory
14 questions
1
vote
0
answers
116
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
- 9,330
3
votes
1
answer
117
views
information theoretic lower bound for hashing functions [closed]
The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store $\frac1{\ln(2)}$ (~1.44) bits per key. There are some sets though that require 0 ...
5
votes
3
answers
533
views
Is there a quantum analog of Kolmogorov Complexity?
Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar.
Since there is a quantum entropy is it reasonable to ask if there is quantum ...
- 13.9k
2
votes
0
answers
92
views
What are the moments of Kolmogorov Complexity for a Random Variable?
Given a random variable $X$ distributed under some computable distribution $P$ we have,
$$0 \le E[K(X)] - H(P) \le K(P)$$
Where $H(P)$ is the entropy of $P$. I tried using Hoeffding concentration ...
1
vote
1
answer
185
views
Total conditional complexity
By $C(|)$ denote conditional complexity.
By $CT(|)$ denote total conditional complexity.
For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$
but $CT(x|y) \ge n $.
...
- 2,576
8
votes
2
answers
567
views
Where should I learn about Kolmogorov complexity of overlapping substrings?
I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, K(...
- 1,601
9
votes
9
answers
2k
views
Existence of unknowable algorithms ?
Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory.
Is it possible to obtain by purely existential (i.e. non-constructive) means the existence of an algorithm ...
- 5,428
4
votes
1
answer
274
views
Transfinitely iterated limit computability
Call a real $x$ limit computable iff there is a Turing machine $T$ such that, for any $i\in\omega$, there is $t(i)\in\omega$ such that the $i$th entry on the tape is not changed after time $t(i)$ and ...
- 521
29
votes
1
answer
1k
views
Can a string's sophistication be defined in an unsophisticated way?
This question is about sophistication, a way of measuring the amount of "interesting, non-random information" in a binary string, which was proposed by Kolmogorov and others in the 1980s. I'll define ...
- 9,823
5
votes
1
answer
862
views
Turing machines and Ising model
I have currently started a new research line aiming to prove a mapping between a 2-symbol Turing machine and the one dimensional Ising model. The connection is seen by recognizing that a set of ...
- 1,687
3
votes
0
answers
125
views
Is a parametric family which is universally consistent for multiple quantiles impossible?
Suppose I am dead-set on using Bayesian inference on independent and identically distributed data, but I'm lazy and insist on using a parametric likelihood function come what may. I'd be reassured to ...
- 2,791
6
votes
2
answers
710
views
Turing machines that read the entire program tape
Consider a two tape universal Turing machine with a one-way-infinite, read-only program tape with a head that can only move right, as well as a work tape. The work tape is initialized to all zeros and ...
-1
votes
3
answers
845
views
Do all uncountable sets contain elements with infinite Kolmogorov complexity?
Otherwise, if all the elements in a set can be represented by a at most n symbols (finite Kolmogorov complexity), I could count them by creating a n dimensional pairing function. Or atleast, that is ...
12
votes
4
answers
4k
views
reversible Turing machines
Hello,
Let T be a Turing machine such that
1) it operates on the alphabet {0,1},
2) its set of states is A
3) the language it accepts is $L$ .
Does there exists a Turing machine S which also ...
- 3,897