Example of decidable set whose preimage is not decidable I know that if a set is a decidable, there exists an algorithm that enumerates it and prints value 1 if a given element belongs to the set and 0 otherwise. Therefore, its image is decidable, too. I think, though, that this is not true for the preimage of of the set under a partially computable function. Can someone provide an example that might help me to understand it, please?
Consider the set $S$ consisting of everything, and the partially computable function $f$ which on input $n$ simulates the $n$th Turing machine, returning whatever the machine outputs (if it ever halts!). The preimage of $S$ under $f$ is the set of all halting Turing machines, which isn't decidable.