16-й: Все сообщения за 22 Ноября 2021 года

Sandro> ...и вот что важно: любая программа для машины Тьюринга исполнима на любой цифровой машине с достаточной памятью. То есть, если программа работает на ней, то она будет работать везде.

Непонятно, почему это важно.
Вроде как сам Тьюринг и доказал, что проблема остановки его машины неразрешима аналитически.
Т.е. чтобы что-то там доказать про исполнимость, надо сначала забабахать весь код алгоритма на этом страшно неудобном эмуляторе, отладить каким-то мозголомным способом, затем дождаться его окончания (крайне не оптимизированного), и только после этого что-то прояснится.
Какой в этом практический смысл?

•  5
•  инфо
•  инструменты
• Ответить на сообщение

Zenitchik> Потому что это точка отсчёта. Позволяет ввести понятие Тьюринг-полного языка и критерии для определения полноты по Тьюрингу.

Звучит, конечно, громко.
"Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию."
Могу я на своем телефоне эмулировать машину Тьюринга, за исключением бесконечной ленты памяти? Могу. Все. У меня в телефоне полнота по Тьюрингу.
И? Легче мне стало?

Zenitchik> На Тьюринг-полном языке можно реализовать любой алгоритм (то, что Тьюринг называет алгоритмом). На неполном - нелюбой.

То же самое. Поди, заморишься искать язык, не "Тьюринг-полный". Ибо сложно представить что-то более примитивное.
Опять же, и? Что это дает?

•  4
•  инфо
•  инструменты
• Ответить на сообщение