Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length.

Can we always find $f:\Sigma^*\to L$ computable in polynomial time in length and such that $f(\Sigma^*)$ is infinite?

  • 1
    $\begingroup$ How would you certify for the input that $L$ indeed contains a word of every length? $\endgroup$
    – Gamow
    Jul 6, 2021 at 12:21
  • $\begingroup$ Every nonempty recursively enumerable language $L$ is the image of a polynomial-time function $f\colon\Sigma^*\to L$. $\endgroup$ Jul 6, 2021 at 17:08
  • $\begingroup$ @EmilJeřábek Do you have a more detailed argument? $\endgroup$
    – deryll
    Jul 7, 2021 at 5:27
  • $\begingroup$ @Gamow I don't have an example right now but it probably should be possible to give a constructive proof with performance worse than polynomial $\endgroup$
    – deryll
    Jul 7, 2021 at 5:36
  • $\begingroup$ Fix $x_0\in L$, and a TM $M$ such that $M(x)$ halts iff $x\in L$. Define $f(w)$ as $x$ if $w$ is a sequence of configurations encoding a halting run of $M$ on an input $x$, and as $x_0$ if $w$ is not such a sequence. $\endgroup$ Jul 7, 2021 at 7:58


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy