2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.