# Tag Info

## New answers tagged kolmogorov-complexity

2

One simple encoding is to represent each of the $N$ states by a partial function $f_n:\{0,1\} \rightarrow \{1, \dots, N\}$. Input $x$ in state $n$ will cause a transisition to state $f_n(x)$ if $f_n(x)$ exists and an error condition if not. You can assume that the initial state is always state $1$. For $N$ states there are $(N+1)^2$ such partial functions (...

Top 50 recent answers are included