Are computable sets closed under XOR?

324 Views Asked by At

How do I prove if computable are/are't closed under XOR?

1

There are 1 best solutions below

0
On

If a set $X$ is computable, you have an algorithm $T_X(x)$ that returns true if $x$ is in $X$ and false otherwise.

Given two computable sets, the algorithm defined by $T_{A \triangle B}(x)=T_A(x) \,\operatorname{XOR}\, T_B(x)$ implies $A\triangle B$ is computable.