New answers tagged computability
0
Modular counting gates are probably the closest thing in complexity theory to what you're asking about. Modular gates sum their inputs and compare against 0 mod $p$. Many authors consider these gates as taking in values in the range $[0,p-1]$ since you can hook multiple wires between pairs of gates. This paper provides a good summary of results in the area ...
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 ...
0
It is computable.
Although $M$ is incomputable, since $M(x)\sim 2^{-K(x)}$, the sequence $\omega$ generated by $argmax M$ would have quite low Kolmogorov complexity.
If the sequence is generated by $argmin M$, then it would be Martin-lof random.
Top 50 recent answers are included
