0
$\begingroup$

I'm reading A Note on a Theorem by Ladner by Balcazar and Diaz, trying to understand the proof of Theorem 2.1. I don't know if it's just old notation, but I'm having quite a bit of trouble.

  1. In step (a), is $\lambda$ the empty string?
  2. In step $(c1)$, it lists a sequence as $T(\lambda),T(0),T(0^2),\cdots,T(0^1)$. I don't see an obvious pattern defining this sequence, what is the sequence? And what's the difference between $T(0)$ and $T(0^1)$?
  3. In step $(c3)$, what does it mean that $T$ will "try to find" a $z$ satisfying those properties? How does it "try" to find it?
  4. The definition of the transducer $T$ and the language $L_{m+1}$ seems circular. Why do we not run into a chicken and egg conundrum?
Improve this question
$\endgroup$

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .