Как использовать теорему Райса за 5 минут

Описание: Здесь мы рассмотрим язык машин Тьюринга, принимающий не более трёх строк, и покажем с помощью теоремы Райса, что он неразрешим. Ключевым моментом является указание на то, что THREE_TM — нетривиальное свойство языков машин Тьюринга. Я покажу, как это сделать в общем случае, а также когда следует использовать теорему Райса, а когда — нет.

Сайт Easy Theory: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theor...
Patreon:   / easytheoryyt  
Fourthwall: https://easy-theory-llc-shop.fourthwa...
Канал решения задач: @easytheoryprobsolve

Временные метки:
0:00 — Вступление
0:54 — Шаг 0: можно ли применить теорему Райса?
1:30 — Шаг 1: Свойство языков машин Тьюринга
2:45 — Шаг 2: Свойство нетривиально
4:25 — Заключение доказательства

Если вам понравился этот контент, пожалуйста, подпишитесь на мой канал:    / @easytheory  

▶ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ◀
1. Что насчёт ТМ, принимающих не более 3 строк и имеющих не более 7 состояний?
2. Что насчёт ТМ, принимающих не менее 0 строк?