1 Coding
1.1 Using For-Transducers
Code the following functions
Describe the number of nested loops used.
1.2 First order !
Let \(L\) be a first-order definable language. White a monotone for-program that computes \(\mathbf{1}_{L}\), i.e., a for-program where the only possible assignment of variables is \(x := \top\).
1.3 Polyblind
We define polyblind for-transducers are those where only the innermost variable loop can be tested against.
- Prove that those programs do not compose.
- Prove that the squaring function (without underscores) is polyblind.
- Prove that the squaring function (with underscores) is not polyblind.
- Prove that the function that maps \(i\) to \(\sum_{j \leq i} j\) is polyblind.
- Prove that the function that maps \(i\) to \(\sum_{j \leq i} j\) can be realised by a monotone for-program.
- Can the function \(i \mapsto \sum_{j \leq i} j\) be realised by a blind and monotone for-program?