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?
7
-
1$\begingroup$ How would you certify for the input that $L$ indeed contains a word of every length? $\endgroup$– GamowJul 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$– Emil JeřábekJul 6, 2021 at 17:08
-
$\begingroup$ @EmilJeřábek Do you have a more detailed argument? $\endgroup$– deryllJul 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$– deryllJul 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$– Emil JeřábekJul 7, 2021 at 7:58
|
Show 2 more comments