Назовем производительностью машины Тьюринга (мТ) целое число, равное:

Если мТ, запущенная на пустой ленте, останавливается, когда на ленте имеется единственный блок единиц, то производительность = длине этого блока

0 в противном случае.

Рассмотрим F(x) = (производительность самой производительной мТ с х местами). Доказано, что эта функция невычислима (Булос Дж., Джеффри Р. "Вычислимость и логика"). Но тем интереснее её вычислять! Предлагаю, устроить конкурс (как с роботами в лабиринте) на построение наипроизводительнейшей мТ с заданным числом мест.

С уважением, Алексей

P.S. Если сообществу интересно, надо уточнить постановку, а то мТ бывают разные