Чем плоха машина Тьюринга
Граждане тут интересуются, а чего вообще в машине Тьюринга плохого? Ведь это-де - самый простой набор правил, при помощи которых можно реализовать любой алгоритм. Не на таком ли надо изучать «общие закономерности»?
Отвечаю.
Во-первых, «самых простых наборов» сильно больше одного. И вовсе не обязательно, что первый изобретённый будет самым удачным. Ведь «простой» в данном случае означает «минимально необходимое количество правил», а вовсе не «наиболее простые для практического использования правила».
Ассемблер, например, в своей редуцированной форме (то есть без спец-команд, заточенных под наиболее часто употребляющиеся действия, которые реализованы на уровне процессора) тоже очень простой и тоже близкий к «необходимому минимуму». Но на нём вполне возможно написать хоть что-то реально полезное. И таки да, пишут.
Однако, во-вторых, «самый простой по количеству правил» вдобавок вовсе не означает «самый простой для использования и анализа». О нет, тут закономерность совсем даже не такая.
Если вы, например, решите все числа записывать в стиле «s(s(s(s(1))))», то у вас вроде бы не будет правил, определяющих позиционную систему записи. Но рассуждать и искать ошибки вам станет гораздо тяжелее, чем если вы вместо вышеприведённого напишете «5». Причём особенно выпукло это проявится, если у вас не «5», а «175234» - в этом случае «самая простая запись» окажется настолько опупенной длины, что вряд ли хоть кто-то сумеет проверить, а не вкралась ли ошибка в запись этого числа.
Аналогично, если ваш графический редактор умеет только ставить точку такого-то цвета по таким-то координатам, то он, конечно, гораздо проще, чем какой-нибудь Фотошоп. Однако рисовать в нём вам будет совсем даже не проще. И даже проверять алгоритм рисования чего-то там тоже будет на многие порядки тяжелее.
Просто по той причине, что масштабируемость и модульность - важное свойство и реализации, и анализа. Чем проще на некотором языке не повторять код, тем проще на нём писать, в среднем. Чем короче в нём запись наиболее часто используемого, тем проще на нём писать. И, конечно, тем проще проверять написанное на наличие ошибок. И, конечно, тем проще анализировать закономерности.
Да, если сделать для любой сущности, которую мы сможем изобрести, свою собственную конструкцию, то тоже будет тяжело, однако…
Представим себе человеческий язык, в котором всего пять слов. И абсолютно все понятия выражаются комбинациями этих пяти. Легко будет на нём говорить? Быстро ли? Легко ли будет понимать сказанное? Легко ли будет анализировать связи понятий, выраженные на этом языке?
Если для «коровы, сидящей на ёлке с вертолётом в зубах» завести своё собственное слово, то тоже, разумеется, будет тяжелее. Но если «корова» с «ёлкой» требуют для своего именования трёх страниц совершенно нечитаемых комбинаций, то так даже хуже.
Модульность и масштабируемость, в общем.
Современные языки, в отличие от машины Тьюринга, закручены вокруг модульности и масштабируемости. С тем или иным успехом, но все они на многие порядки более удачны, чем оная машина.
Теперь, если показать сводимость каждого языка программирования к любому нами выбранному (а заодно и реализуемость оного на машине Тьюринга, если хоть кто-то всё ещё видит в этом смысл), то этот язык будет на порядки более хорош для «теоретического изучения программирования и алгоритмов». Просто по той причине, что на машине Тьюринга даже сортировку списка чисел пузырьком хрен кто за разумное время напишет (а если вдруг напишет, то хрен потом проверит, что там нет ошибок), а на любом современном языке это сделает за полчаса даже старательный дошкольник.
Соответственно, проще писать, проще рассуждать, проще проверять, проще анализировать, проще вычленять закономерности. А способность переносить выводы на другие языки - та же. Или даже проще, поскольку очень многие конструкции повторяются почти один в один.
Что ещё, в-третьих, немаловажно, на современных языках до хрена всего уже написано. А раз оно уже написано, то нет сомнений, что его можно написать. Поэтому, в отличие от машины Тьюринга, для которой даже простейшие по нынешним временам вещи не очевидны, про целый ряд вещей будет точно известно, что они реализуемы - даже с примерами, как именно реализуемы. Поэтому соблазна доказать, что Фотошоп невозможен, уже не будет.
Я вообще думал, что в двадцать первом веке такие вещи уже очевидны всем. Но нет, многие, видимо, любят, когда сто́я, в гамаке и в противогазе - иначе крутость неясна. Типа, «чем реализовать распознавание образов хитровывернутой нейросетью, я лучше за в сто раз большее время реализую вычисление логарифма на машине Тьюринга и сделаю из этого вывод, что на Тьюринг-полном языке его можно реализовать».
Хотя вроде бы, если сравнить успехи изучателей машины Тьюринга за последний век и успехи программистов на нормальных языках даже за последнюю пару десятилетий, сразу ясно, где больше крутости.
doc-файл
публикация в блоге автора
Отвечаю.
Во-первых, «самых простых наборов» сильно больше одного. И вовсе не обязательно, что первый изобретённый будет самым удачным. Ведь «простой» в данном случае означает «минимально необходимое количество правил», а вовсе не «наиболее простые для практического использования правила».
Ассемблер, например, в своей редуцированной форме (то есть без спец-команд, заточенных под наиболее часто употребляющиеся действия, которые реализованы на уровне процессора) тоже очень простой и тоже близкий к «необходимому минимуму». Но на нём вполне возможно написать хоть что-то реально полезное. И таки да, пишут.
Однако, во-вторых, «самый простой по количеству правил» вдобавок вовсе не означает «самый простой для использования и анализа». О нет, тут закономерность совсем даже не такая.
Если вы, например, решите все числа записывать в стиле «s(s(s(s(1))))», то у вас вроде бы не будет правил, определяющих позиционную систему записи. Но рассуждать и искать ошибки вам станет гораздо тяжелее, чем если вы вместо вышеприведённого напишете «5». Причём особенно выпукло это проявится, если у вас не «5», а «175234» - в этом случае «самая простая запись» окажется настолько опупенной длины, что вряд ли хоть кто-то сумеет проверить, а не вкралась ли ошибка в запись этого числа.
Аналогично, если ваш графический редактор умеет только ставить точку такого-то цвета по таким-то координатам, то он, конечно, гораздо проще, чем какой-нибудь Фотошоп. Однако рисовать в нём вам будет совсем даже не проще. И даже проверять алгоритм рисования чего-то там тоже будет на многие порядки тяжелее.
Просто по той причине, что масштабируемость и модульность - важное свойство и реализации, и анализа. Чем проще на некотором языке не повторять код, тем проще на нём писать, в среднем. Чем короче в нём запись наиболее часто используемого, тем проще на нём писать. И, конечно, тем проще проверять написанное на наличие ошибок. И, конечно, тем проще анализировать закономерности.
Да, если сделать для любой сущности, которую мы сможем изобрести, свою собственную конструкцию, то тоже будет тяжело, однако…
Представим себе человеческий язык, в котором всего пять слов. И абсолютно все понятия выражаются комбинациями этих пяти. Легко будет на нём говорить? Быстро ли? Легко ли будет понимать сказанное? Легко ли будет анализировать связи понятий, выраженные на этом языке?
Если для «коровы, сидящей на ёлке с вертолётом в зубах» завести своё собственное слово, то тоже, разумеется, будет тяжелее. Но если «корова» с «ёлкой» требуют для своего именования трёх страниц совершенно нечитаемых комбинаций, то так даже хуже.
Модульность и масштабируемость, в общем.
Современные языки, в отличие от машины Тьюринга, закручены вокруг модульности и масштабируемости. С тем или иным успехом, но все они на многие порядки более удачны, чем оная машина.
Теперь, если показать сводимость каждого языка программирования к любому нами выбранному (а заодно и реализуемость оного на машине Тьюринга, если хоть кто-то всё ещё видит в этом смысл), то этот язык будет на порядки более хорош для «теоретического изучения программирования и алгоритмов». Просто по той причине, что на машине Тьюринга даже сортировку списка чисел пузырьком хрен кто за разумное время напишет (а если вдруг напишет, то хрен потом проверит, что там нет ошибок), а на любом современном языке это сделает за полчаса даже старательный дошкольник.
Соответственно, проще писать, проще рассуждать, проще проверять, проще анализировать, проще вычленять закономерности. А способность переносить выводы на другие языки - та же. Или даже проще, поскольку очень многие конструкции повторяются почти один в один.
Что ещё, в-третьих, немаловажно, на современных языках до хрена всего уже написано. А раз оно уже написано, то нет сомнений, что его можно написать. Поэтому, в отличие от машины Тьюринга, для которой даже простейшие по нынешним временам вещи не очевидны, про целый ряд вещей будет точно известно, что они реализуемы - даже с примерами, как именно реализуемы. Поэтому соблазна доказать, что Фотошоп невозможен, уже не будет.
Я вообще думал, что в двадцать первом веке такие вещи уже очевидны всем. Но нет, многие, видимо, любят, когда сто́я, в гамаке и в противогазе - иначе крутость неясна. Типа, «чем реализовать распознавание образов хитровывернутой нейросетью, я лучше за в сто раз большее время реализую вычисление логарифма на машине Тьюринга и сделаю из этого вывод, что на Тьюринг-полном языке его можно реализовать».
Хотя вроде бы, если сравнить успехи изучателей машины Тьюринга за последний век и успехи программистов на нормальных языках даже за последнюю пару десятилетий, сразу ясно, где больше крутости.
doc-файл
публикация в блоге автора