New answers tagged lo.logic
9
Maybe the keyword you are looking for is "Implicit Complexity". It is more general than Curry-Howard correspondence, but several lines of research investigate along the axis you are interested in. You can check for instance the publications of Patrick Baillot for many references and pointers.
For a little self-promotion, here are for instance two ...
2
This can take exponentially many steps, as Laakeri explained.
You can build a system that cycles with period $p$. In particular, the update rule is $x_i = x_{i-1 \bmod p}$ for all $i$, with variables $x_0,\dots,x_{p-1}$.
Let $p_1,\dots,p_k$ be the first $k$ primes. Concatenate $k$ disjoint systems, each of which cycles with period $p_i$. Then the period ...
Top 50 recent answers are included
