Доказательство языка неразрешимо, используя сокращения Тьюринга

Question

Мне нужно доказать, что язык L(EVEN) = { M : |L(M)| is even } неразрешим.

Другими словами, язык L(EVEN) - это совокупность всех машин Тьюринга, которые принимают некоторый язык даже кардинального числа.

Здесь M - кодировка некоторой машины Тьюринга, которая будет передана в качестве ввода, если существует решатель для L(EVEN).

Я выполнил другие проблемы, аналогичные этой один с использованием сокращений Тьюринга, один пример можно увидеть здесь:

Моя проблема в том, что я не могу придумать какой-то ранее доказанный неразрешимый язык, который было бы полезно показать L <= L(EVEN).

Неразрешимые языки, которые мы уже рассмотрели в классе, таковы:

- L(emptyset) = { M | M is a TM and |L(M)| = emptyset}  
- L(ACC) = { (M, x) | M is a TM, and M accepts input x}  
- L(HALT) = { (M, x) | M is a TM, and M halts on input x}  
- L(EQ) = { (M1, M2) | M1, M2 are TMs, and L(M1) == L(M2) }  
- L(∈ - HALT) = { M | M is a TM, M halts on input ∈ } 

Я также мог бы использовать дополнения этих языков, поскольку разрешимость закрыта при дополнении. Как я мог использовать один из этих неразрешимых языков, чтобы доказать, что L (ДАЖЕ) также неразрешим, используя настройку, аналогичную приведенной в качестве примера проблеме?

Answer 1

Предположим, у нас был решатель для L (ДАЖЕ). Затем мы можем определить L (A CC) следующим образом:

От входа M к TM для L (A CC), построить TM M ', который сначала проверяет, является ли входная лента входной х в М, а затем запускает М на х. Конструкция M 'либо принимает язык {x}, если M принимает x, либо пустой язык, если M этого не делает.

Используя наш решатель для L (EVEN) в кодировке M', мы можем сказать, если | L (M ') | является четным (в этом случае L (M ') пустым, а M не принимает x) или нечетным (в этом случае L (M') = {x} и M принимает x).