Some questions about the Computability of Turing Machines I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines.

Consider we have the partial functions $f,g,h,t: \mathbb{N} \rightarrow \mathbb{N}$ with $f$ is Turing Machine computable, $g$ not Turing Machine computable, $h$ is not While solvable and $t$ is While computable. Are the following answers correct? And is there anything changing if we had an non deterministic TM?

There is no proof to do words are ok :)


Is $f \circ g$ Turing Machine computable?
Is $g \circ f$ Turing Machine computable?
Is $t \circ h$ While computable?
Is $h \circ t$ While computable?


My answers:

First of all, we know that Turing Machine = While Computability. (#)


I would say, that we do not know if it is or is not TM computable, because there may a TM who can handle the output of an not TM computable function.
I would say no, because if whatever $g$ takes, it won't be TM computable.
and 4. Because  of (#) it is the same like 1. and 2.


Could that be right? It is for an multiple choice test and those questions are tricky.
The answer is "we don't know without more information" for all 4.

Suppose $f$ is the identity function $f(x) = x$. Then $f \circ g = g \circ f = g$, which is non-computable.

On the other hand, suppose $g$ is a total non-computable function (which is a special case of $g$ being a partial non-computable function), and suppose $f$ is the constant zero function $f(x) = 0$. In this case:


$f \circ g$ is the constant zero function, which is obviously computable.
$g \circ f$ is also a constant function. We don't necessarily know what the constant is, but that doesn't matter; every constant function is computable. See How can it be decidable whether $\pi$ has some sequence of digits?


Deterministic vs. non-deterministic Turing machine doesn't affect the answer, because a deterministic Turing machine can simulate the execution of a non-deterministic Turing machine (potentially with an exponential slowdown) by dovetailing.