On my favourite TCS site cstheory.stackexchange.com I found a simple question about the Post Correspondence Problem: If the upper and lower words of each domino must have different lengths, is the problem still undecidable? (we call this variant $PCP^{\neq}$). The Continue reading
This is a simple note on Turing completeness of 2-neighbourhood 1-dimensional Cellular Automata. A Cellular Automaton (pl. Cellular Automata) is a model of computation based on a grid of cells that evolve according to a simple set of rules. The Continue reading
( A few lines where incompressibility meets unprovability ) The Kolmogorov Complexity $K(x)$ of a string $x$ relative to an Universal Turing machine $U$ is the length of the shortest program $p$ that prints $x$: $$K(x) = min\{ p \mid U(p) = Continue reading
While thinking about simple puzzles that seem hard at a first glance, but have not enough rules and structural constraints that make it easy to prove that they are NP-complete, I designed the following game (but perhaps it has already Continue reading
It is well known that $\text{Primes}= \{ a^p \mid p \text{ is prime}\}$ is not regular. The standard proof uses the pumping lemma for regular languages, but you can also use Parikh s theorem or Myhill-Nerode theorem: see this question on Continue reading
I just bought the nice book Problems with a POINT Exploring Math and Computer Science by William Gasarch and Clyde Kruskal. The book explains many nice mathematical and theoretical computer science problems that are easy-to-understand-but-not-so-easy-to-solve , and most of them Continue reading
What happens if a modern constraint satisfaction and optimization program decides to play a Video Game Classic? I m a fan of old Video Games (80s games) and recently I found an interesting debate about the world record of the Atari s Continue reading
A one-state Turing machine is a very weak device: it has no internal memory and it cannot even recognize the trivial language $L = \{1\}$. Its transition function is a simple map $\delta : \Sigma \to \Sigma \times \{L,R\}$, i.e. Continue reading
After a long time, here we are again let s resume with a small (and rather trivial) post Busy Beavers are allmost incompressible! easy fact, but I didn t find it anywhere. Let $\sigma(M)$ be the number of $1$s Continue reading
Recently A. Amarilli (a3nm) posted a question on cs.stackexchange.com about the computational complexity of a Test Round problem of the Google France #Hash Code 2015: the Pizza Regina problem (March 27th, 2015): Definition [Pizza Regina problem] Input: A grid $M$ Continue reading