Experiment 1: context free language 1n2n

• Goal: given n, push sequence of n 1’s and n 2’s. Additional primitives: 1toD(); 2toD()

• 1s, n=1: (defnp 2toD)

• 10s, n=2: (defnp 2toD grt c2 c2 endnp)

• 1min, n=3: (defnp 2toD grt c2 c2 endnp boostq delD delD bsf 2toD)

• 1h, n=4: (defnp 2toD grt c2 c2 endnp boostq delD delD bsf 2toD fromD delD delD delD fromD bsf by2 bsf)

• +2min, n=5: (defnp 2toD grt c2 c2 endnp boostq delD delD bsf 2toD fromD delD delD delD fromD bsf by2 bsf by2 fromD delD delD fromD cpnb bsf) unelegant, lengthy, but sufficient for n=1...5

• 0.3 days, n=1,2,3,4,5,6: (defnp c1 calltp c2 endnp) elegant!

• +20ms: n=7, n=8, …, n=30: by same recursive program.

Previous slide

Next slide

Back to first slide

View graphic version