Γλώσσες L1 και L2 τέτοιες ώστε η μία να είναι Turing αποφασίσιμη

(Α) Έστω δύο οποιεσδήποτε γλώσσες L1, L2 υποσύνολο Σ*. Δείξτε ότι
(1) Αν οι L1 και L2 είναι Turing αποφασίσιμες τότε και η L1^οL2   είναι Turing
αποφασίσιμη.

(2) Υπάρχουν γλώσσες L1 και L2 τέτοιες ώστε η μία να είναι Turing αποφασίσιμη, η
άλλη  να  είναι Turing αποδεκτή (και  όχι Turing αποφασίσιμη) και η  L1^οL2  να μην
είναι Turing αποφασίσιμη.
Σημείωση: Με L1^οL2  συμβολίζουμε την συνένωση των γλωσσών L1 και L2.

(Β) Αποδείξτε ότι για μια οποιαδήποτε γλώσσα Lυποσύνολο  Σ* και την συμπληρωματική της,
L’, ένα από τα παρακάτω μπορεί να συμβεί:
(1) Η L είναι Turing αποφασίσιμη και η L’ είναι Turing αποφασίσιμη.
(2) Μία από τις L και L’ είναι Turing αποδεκτή (και όχι Turing αποφασίσιμη) και
η άλλη δεν είναι Turing αποδεκτή.
(3) Η L δεν είναι Turing αποδεκτή και η L’ δεν είναι Turing αποδεκτή.

Σημείωση: Με Σ συμβολίσουμε το αλφάβητο σύμφωνα με το οποίο ορίζονται οι
γλώσσες του ερωτήματος.