Назовем производительностью машины Тьюринга (мТ) целое число, равное:
Если мТ, запущенная на пустой ленте, останавливается, когда на ленте имеется единственный блок единиц, то производительность = длине этого блока
0 в противном случае.
Рассмотрим F(x) = (производительность самой производительной мТ с х местами). Доказано, что эта функция невычислима (Булос Дж., Джеффри Р. "Вычислимость и логика"). Но тем интереснее её вычислять! Предлагаю, устроить конкурс (как с роботами в лабиринте) на построение наипроизводительнейшей мТ с заданным числом мест.
С уважением, Алексей
P.S. Если сообществу интересно, надо уточнить постановку, а то мТ бывают разные
Здравствуйте, Les, Вы писали:
Les>Назовем производительностью машины Тьюринга (мТ) целое число, равное:
Les>Если мТ, запущенная на пустой ленте, останавливается, когда на ленте имеется единственный блок единиц, то производительность = длине этого блока
Les>0 в противном случае.
Les>Рассмотрим F(x) = (производительность самой производительной мТ с х местами). Доказано, что эта функция невычислима (Булос Дж., Джеффри Р. "Вычислимость и логика"). Но тем интереснее её вычислять! Предлагаю, устроить конкурс (как с роботами в лабиринте) на построение наипроизводительнейшей мТ с заданным числом мест.
Les> С уважением, Алексей
Les>P.S. Если сообществу интересно, надо уточнить постановку, а то мТ бывают разные
Да уж действительно. x мест — это что? x — состояний? (В моем понимании алгоритм мТ оформляется в виде матрицы состояния X символы на ленте)
Здравствуйте, DOOM, Вы писали:
DOO>Здравствуйте, Les, Вы писали:
Les>>Назовем производительностью машины Тьюринга (мТ) целое число, равное:
...
Les>>P.S. Если сообществу интересно, надо уточнить постановку, а то мТ бывают разные
DOO>Да уж действительно. x мест — это что? x — состояний? (В моем понимании алгоритм мТ оформляется в виде матрицы состояния X символы на ленте)
Да, речь о состояниях. А на счет _представления_ мТ — я предпочитаю граф переходов, ИМХО гораздо нагляднее.
Здравствуйте, yogi, Вы писали:
Y>Здравствуйте, Les, Вы писали:
Les>>Назовем производительностью машины Тьюринга (мТ) целое число, равное:
Les>>Если мТ, запущенная на пустой ленте, останавливается, когда на ленте имеется единственный блок единиц, то производительность = длине этого блока
Y>Что за пурга? "Пустая лента" и "на ленте имеется ... блок единиц" взаимоисключающие понятия, мне кажется.
Не пурга а метель. Вы не в курсе что мТ может изменять состояние ленты?
