2022 Developer Survey is open! Take survey.

New answers tagged

2 votes

Establishing competing memory limits for pushdown automata

This answer is inspired by this question. The conjecture is false, for the following reason. Consider the alphabet $\Sigma=\{0,1\}$, and the language $A=\{0^n1(0|1)^n|n>0\}$. This language is ...
user avatar
  • 7,350
2 votes

Reversible Turing tarpits?

Many years ago I created a language called Kayak (language spec, esolangs.org entry) that was meant to be a reversible-computing tarpit. It's slightly less primitive than Reversible Brainfuck, since ...
user avatar
  • 176

Top 50 recent answers are included