Пересечение двух разрешимых по Тьюрингу языков разрешимо по Тьюрингу

Question

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

Я знаю, что язык является разрешимым по Тьюрингу, если существует алгоритм для определения членства. Однако я не уверен, с чего начать с этого доказательства.

Любая помощь приветствуется!

Answer 1

Сначала нужно определить, что такое пересечение. Это набор всех строк, которые являются членами обоих языков.

Поскольку оба языка являются разрешимыми, это означает, что для каждого существует такой алгоритм. Вам нужно доказать, что с помощью этих алгоритмов вы можете получить новый алгоритм, который решает принадлежность строк в пересечении.

Подсказка: алгоритм, который отвечает "да", если и только если строка на обоих языках.