Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain

Question

The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of infinite words, and finite words over $\Sigma$. The book is concerned with Type-2 computability, which defines computability over infinite words. Then a function $f : \subseteq \Sigma^{\omega} \to \Sigma^{\ast}$ is called computable iff there exists a Turing machine reading its input on a read-only tape from left to right (without going back), and outputting symbols on its output tape without the ability to go back, i.e. what is written once could not be erased. This is called Type-2 computability (or a Type-2 machine).

Statement: A function $f :\subseteq \Sigma^{\omega} \to \Sigma^{\ast}$ is computable, iff $f = h_{\ast}$ for some computable function $h :\subseteq \Sigma^{\ast} \to \Sigma^{\ast}$ with prefix-free domain.

Proof: Let $M$ be a Type-2 machine computing $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$. Define $h :\subseteq \Sigma^{\ast} \to \Sigma^{\ast}$ by $$ h(w) := \left\{\begin{array}{ll} f(w0^{\omega}) & \mbox{if on input $w0^{\omega}$ the machine $M$ halts after exactly $|w|$ steps} \\ \mbox{div} & \mbox{otherwise.} \\ \end{array}\right. $$ Then $h$ is computable, has prefix-free domain and satisfies $f = h_{\ast}$. [...]

I am unsure about $f = h_{\ast}$. Surely if $h_{\ast}(p) = u$, then $h(w) = u$ for some $w \in \mbox{dom}(h)$ with $w \sqsubseteq p$. By the defintion of $\mbox{dom}(h)$ this mean the machine halts on $w0^{\omega}$ in exactly $|w|$ steps, hence has read at most $|w|$ symbols, and thereby exhibiting the same behavior on $p$, i.e. we have $f(p) = u$.

But now I want to show that if $h_{\ast}(p)$ diverges, then $f$ diverges too, or, giving the same, that if $f(p) = u$ then $h_{\ast}(p) = u$. But for example suppose $f(p) = u$, and let $k$ be the steps taken by the machine reading $p$ to halt and produce $u$, then surely the prefix $v$ of $p$ read in this process has at most length $k$. But as $|v| < k$ is possible, we could not conclude that $v \in \mbox{dom}(h)$, but by padding $v$ with zeros we know $v0^{k - |v|} \in \mbox{dom}(h)$ by definition, and hence $h_{\ast}(v0^{\omega}) = h(v0^{k - |v|})$ so that $f(p) = h_{\ast}(v0^{\omega})$. But this is all I get, I do not see how to conclude $h_{\ast}(p) = f(p)$, as this would mean we have some prefix $x$ from $p$ such that the machine takes exactly $|x|$ steps in producing $u$, but in general we cannot conclude that $v0^{k - |v|}$ is a prefix of $p$ if $k - |v| > 0$.

So why does this result holds? And why $h_{\ast} = f$?

Answer 1

I guess I have an alternative solution. Let $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$ be computable. Define $$ h(u) = v \mbox{ iff } f(u\Sigma^{\omega}) = \{v\} \mbox{ with $u$ minimal} $$ and let $h(u)$ diverge otherwise. Then $\mbox{dom}(h)$ is prefix-free for if $h(u) = v$ then $f(u\Sigma^{\omega}) = \{v\}$ as the machine behaves the same when reading the prefix $u$, producing $v$. Also $h$ is computable, for if $M$ is a machine for $f$ and $u \in \Sigma^{\ast}$, just simulate $M$ on $u0^{\omega}$ and if it produces some output and stops check if the prefix read by $M$ equals $u$; and if not just enter an infinite loop.

Furthermore we have $f = h_{\ast}$. For if $f(p) = u$ then there exists some minimal prefix $w \sqsubseteq p$ with $f(w\Sigma^{\omega}) = \{u\}$, hence $h_{\ast}(p) = h(w) = u$. For the other direction suppose $h_{\ast}(p) = u$, then $w \sqsubseteq p$ with $h(w) = u$, i.e. $f(w\Sigma^{\omega}) = \{u\}$, in particular $f(p) = u$.