# Questions tagged [algorithmic-randomness]

Martin-Löf randomness and other randomness notions arising from computable tests; as well as related concepts such as Kolmogorov complexity, K-triviality, and effective Hausdorff dimension.

**0**

votes

**0**answers

71 views

### Finding Elusive Orbits in GL action on polynomials

I am attempting to generate orbit representatives for the action of $\operatorname{GL}(n, F_2)$ on homogeneous polynomials of fixed degree $d$ in $n$ variables using random methods.
However, some ...

**1**

vote

**1**answer

124 views

### Find probability of non-stationary inputs into Turing machine?

Consider some finite string $x=(x_1,x_2,...,x_{n-1},x_n)$ that is drawn from a non-stationary process. Would it be possible to use the algorithmic probability formula, defined by Solomonoff as,
$$
P_M(...

**4**

votes

**2**answers

191 views

### Example of concrete statement which requires probabilistic algorithm

In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...

**5**

votes

**0**answers

109 views

### Subsequence of a sequence of digits of an algebraic irrational number

Consider an algebraic irrational number in $(0,1)$ with binary expansion
$x = \sum_{n\ge 1} \frac{a_n}{2^n}$. Is it possible that the number $\sum_{n\ge 1}\frac{a_{2n}}{2^n}$ is again algebraic ...

**4**

votes

**1**answer

323 views

### Existence of normal number except random numbers

For normality, see https://en.wikipedia.org/wiki/Normal_number. For random number/sequence, see https://en.wikipedia.org/wiki/Algorithmically_random_sequence.
Now, is there any number that is normal ...

**0**

votes

**1**answer

79 views

### Randomness defined in Kolmogorov complexity is identified with one in probability theory/stochastic process?

Actually, in many works of probability theory/stochastic process, there is no explicit definition of randomness. Maybe because we think we can deduce the definition easily.
But in Kolmogorov ...

**7**

votes

**1**answer

442 views

### What is the precise relation between Kolmogorov complexity and Shannon's entropy?

Consider the discrete case:
Shannon's entropy is $H(x)=-\sum\limits_i^n p(x_i) log\space p(x_i)$.
Probability based on prefix-free Kolmogorov complexity is $R(x_i)=2^{-K(x_i)}$ where $K(x_i)$ is ...

**2**

votes

**1**answer

148 views

### Generating an arbitrarily long sequence with decreasing Kolmogorov complexity of terms

Is there an algorithm which, given a string $s$, generates a sequence of $|s|$ strings, such that it can be proven in some axiomatic system $S$, that the Kolmogorov complexity of each successive ...

**2**

votes

**0**answers

97 views

### Non-uniform distribution in digits of chaotic orbits?

For a class I was teaching, I was demonstrating time-series analysis with the famous discrete-time dynamical system $x_{n+1} = ax_n(1-x_n)$, where $a = 4 - \epsilon$ ($\epsilon$ ``small'') and ...

**3**

votes

**0**answers

395 views

### A question about the Chaitin constant of a theory

Chaitin's famous incompleteness theorem states that for every r.e. theory $T\supseteq Q$ in the language of arithmetic, there is a constant $d_T$ such that for any $m\geq d_T$ and any $x$, $T$ can ...

**3**

votes

**0**answers

228 views

### “Kolmogorov complexity” of models of computation

This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...

**8**

votes

**0**answers

195 views

### Complete list of exceptions and efficient algorithm for Waring's problem

2 weeks ago, Samir Siksek http://arxiv.org/abs/1505.00647 proved more than 150-years-old conjecture that every positive integer other than 15, 22, 23, 50, 114, 167, 175, 186, 212, 231, 238, 239, 303, ...

**2**

votes

**1**answer

101 views

### Largeness, generic, random points

As presented in Oxtoby's book ( http://link.springer.com/book/10.1007%2F978-1-4615-9964-7 ), there are two notions of largeness for subspace $Y$ of a given space $X$:
Topology: $X$ is a topological ...

**2**

votes

**2**answers

298 views

### Absolutely algorithmically random infinite sequence

Let's call an infinite sequence of bits $f:N\rightarrow \{0,1\}$ absolutely random if any computably constructed subsequence is not computable, i.e. there aren't monotonic computable function $g:N \...

**2**

votes

**0**answers

39 views

### largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...

**1**

vote

**0**answers

138 views

### Kolmogorov complexity proof of Lovasz local lemma

Roughly speaking, the Kolmogorov Complexity proof of Lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, ...

**3**

votes

**1**answer

105 views

### Disobedience of some complete r.e. set to some additive cost function

An additive cost function is defined as $c: \omega\times \omega \to \mathbb{Q}_2$ such that it is recursive, monotonic (i.e. $c(x+1,y)\leq c(x,y)\leq c(x,y+1)$ and $c(x,y)=0$ whenever $x\geq y$, the ...

**3**

votes

**3**answers

650 views

### Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...

**3**

votes

**0**answers

101 views

### Weak randomness relative to finite-state machines

Is there a nice example of a sequence that looks random to any predictor whose predictions use a finite-state machine?
More precisely, consider a finite-state machine $M$ with input alphabet {0,1} ...

**8**

votes

**1**answer

223 views

### Cohesive set with degree below non-high Martin-Löf random reals

A set A is cohesive if $A\subseteq ^* W_e$ or $A\subseteq^* \bar{W_e}$ for each $e\in \omega$ (standard enumeration of r.e. sets). By Jockusch and Stephan's 1993 paper 'A cohesive set which is not ...