Позволяет доказать, что проблема не может быть решена алгоритмически: B (M) = 1, если M - программа Тьюринга и нет ввода для длины строки 2, 4, 6, 8, на которой M останавливается
Моя идея:
M = «На входной строке w :.
- Отсканируйте ленту и отметьте первый 0, который не был отмечен. Если неотмеченный 0 не найден, перейдите к этапу 4. В противном случае верните головку назад к передней части ленты.
- Отсканируйте ленту и отметьте первую 1, которая не была отмечена. Если неотмеченный 1 не найден, отклонить
- Переместите голову назад к передней части ленты и перейдите к этапу 1.
- Переместите голову назад к передней части ленты. Сканируйте ленту, чтобы увидеть, остались ли какие-либо неотмеченные единицы. Если ничего не найдено, примите; в противном случае, откажитесь ».
После выполнения этих алгоритмов, если нет строк для соответствующих размеров, указанных в вопросе, он перейдет в положение по умолчанию и выведет вывод по умолчанию как 1.
Но я действительно не уверен