<p>I'm curious of the ways we can construct provably complex languages.</p>
<p>In particular, most constructions (i.e., the one used for proving the <a href="https://en.wikipedia.org/wiki/Time_hierarchy_theorem" rel="nofollow noreferrer">Time hierarchy theorem</a>) seem to rely on encodings of Turing Machines and some diagonalization argument.</p>
<p><strong>Do we know of ways to construct complex languages based on other techniques?</strong></p>
<p>For example, I'm thinking in the direction of somehow using randomness to construct a difficult to decide language similar to how we would do to achieve high Kolmogorov complexity.</p>

CC BY-SA 4.0
2024-03-17T16:56:25.963Z
A good place to start is [System F](https://en.wikipedia.org/wiki/System_F), also known as  second-order propositional constructive logic. F lacks recursion so is total, and cannot be Turing complete. Unless you know what you are looking for,  you'd probably struggle to find a natural total function that is provably not expressible in System F. Barendregt's [$\lambda$-cube](https://en.wikipedia.org/wiki/Lambda_cube) gives a systematic way of constructure a few more such languages.
Martin Berger
CC BY-SA 4.0
2024-03-18T01:40:49.817Z
This seems essentially the same as https://cstheory.stackexchange.com/q/6575/129. Is there something @mti has in mind that distinguishes the two?
Joshua Grochow
CC BY-SA 4.0
2024-03-18T14:46:23.000Z
@JoshuaGrochow Thanks for the pointer. Looks definitely related and interesting. Will look into that in more detail later. This question does have a different scope though. Beyond getting an overview of methods for constructing complex languages, my intent also was to initiate a discussion around the idea of constructing complex languages more "manually". E.g., we know that a random string has high Kolmogorov complexity. Is there a similar property in the realm of computation that ensures high computational complexity?
mti
CC BY-SA 4.0
2024-03-18T19:08:36.110Z
Just as you prove that random strings have high Kolmogorov complexity w/ a counting argument, one can also prove by a counting argument (going back at least to Shannon) that random Boolean functions on n variables cannot be computed by circuits smaller than $\Theta(2^n / n)$. Is that like what you had in mind?
Joshua Grochow
CC BY-SA 4.0
2024-03-18T19:54:32.270Z
Yes, something like that. Would you have a reference for a formalization of that statement?
mti
<cc.complexity-theory>
Constructing complex languages without "recursion"
mti
# Constructing complex languages without "recursion"

(Asked by: username_0 on 2024-03-17)

I'm curious of the ways we can construct provably complex languages.

In particular, most constructions (i.e., the one used for proving the [Time hierarchy theorem](https://en.wikipedia.org/wiki/Time_hierarchy_theorem)) seem to rely on encodings of Turing Machines and some diagonalization argument.

**Do we know of ways to construct complex languages based on other techniques?**

For example, I'm thinking in the direction of somehow using randomness to construct a difficult to decide language similar to how we would do to achieve high Kolmogorov complexity.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: A good place to start is [System F](https://en.wikipedia.org/wiki/System_F), also known as  second-order propositional constructive logic. F lacks recursion so is total, and cannot be Turing complete. Unless you know what you are looking for,  you'd probably struggle to find a natural total function that is provably not expressible in System F. Barendregt's [$\lambda$-cube](https://en.wikipedia.org/wiki/Lambda_cube) gives a systematic way of constructure a few more such languages.  
> **username_2**: This seems essentially the same as https://cstheory.stackexchange.com/q/6575/129. Is there something @mti has in mind that distinguishes the two?  
> **username_0**: @JoshuaGrochow Thanks for the pointer. Looks definitely related and interesting. Will look into that in more detail later. This question does have a different scope though. Beyond getting an overview of methods for constructing complex languages, my intent also was to initiate a discussion around the idea of constructing complex languages more "manually". E.g., we know that a random string has high Kolmogorov complexity. Is there a similar property in the realm of computation that ensures high computational complexity?  
> **username_2**: Just as you prove that random strings have high Kolmogorov complexity w/ a counting argument, one can also prove by a counting argument (going back at least to Shannon) that random Boolean functions on n variables cannot be computed by circuits smaller than $\Theta(2^n / n)$. Is that like what you had in mind?  
> **username_0**: Yes, something like that. Would you have a reference for a formalization of that statement?  

---

## 0 answers

