Semantic Security may be defined using the distinguishability experiment/game, which we recall as follows:
Let $(E,D)$ be an encryption scheme. After the challenger chooses a security parameter $n$ and random key $k$, the (semantic security) adversary choosing two messages $m_0, m_1$ that depend on $n$. The challenger randomly chooses a bit $b \in \{0,1\}$, provides $E_k(m_b)$ to the adversary who then must decide whether $b$ is $0$ or $1$.
Question: The messages $m_0$ and $m_1$ are of polynomial length in $n$, but are they actually computable functions of $n$? i.e., does the adversary compute $m_0$ and $m_1$ using some Turing machine that runs in polynomial time?
I suspect that the answer is no, they are not computable (but still polynomial length). I base this from trying to prove properties of semantic security such as impossibility of bit guessing and message recovery etc. I also think this is precisely stated in Goldreich's book where there is no generation of the messages and only specification of their polynomial length (but he uses circuit families instead which I am not familiar with) but in the Katz-Lindell it seems that there is ambiguity in this definition.
