сентября 20, 2011

Полнота по Тьюрингу — насколько это хорошо?

Часто любят говорить, что такой-то язык программирования полон по Тьюрингу. Насколько хорошо полнота по Тьюрингу характеризует язык с точки зрения практического применения?

ИМХО, это свойство само по себе ничего не значит, его следует считать обязательным для любого языка программирования. Напротив, если какой-то язык программирования не полон по Тьюрингу, то это очень плохо, плохо настолько, что даёт повод серьёзно задуматься: а является ли этот язык языком программирования?

Например, есть язык программирования BitBitJump, о нём на русском можно почитать тут. Язык состоит всего из одной инструкции: скопировать в памяти один бит в другой, и перейти по заданному адресу (переход происходит в любом случае, т.е. он безусловный). Инструкция имеет три операнда: 1) адрес, откуда копируем, 2) адрес, куда копируем, и 3) адрес, на который будет совершён переход выполнения программы. Важная оговорка: программа и данные находятся в одной памяти вместе, т.е. во время выполнения программа может модифицировать свой код.

Кажется, что на таком языке ничего написать не получится. Однако, в статье, на которую я дал ссылку выше, можно почитать о том, как на этом языке реализовать сложение, умножение, условный переход, указатели и т.д.

Оказывается, что язык BitBitJump полон по Тьюрингу. На нём можно посчитать любую вычислимую функцию.

С точки зрения здравого смысла ясно, что BitBitJump радикально уступает привычным языкам программирования в практическом применении, потому что все они умеют копировать биты и совершать безусловные переходы.

Для оценки именно практичности нужны какие-то другие критерии. Я не знаю, какие именно, но полнота по Тьюрингу на эту роль точно не подходит. Полнота по Тьюрингу скорее полезна в роли эдакого теста на дурака: отметать то, что не является языком программирования, но пытается себя за него выдать.

Например, известен факт, что метапрограммирование (шаблоны в частности) в C++ является полным по Тьюрингу. Но это само по себе вовсе не говорит об удобстве (или неудобстве) в его применении на практике. Если бы метапрограммирование в C++ происходило на языке BitBitJump, то навряд ли это кого-то обрадовало бы, хотя полнота по Тьюрингу сохранилась бы.


Комментариев нет:

Отправить комментарий

Постоянные читатели

Обо мне

Моя фотография
Мой e-mail: vitek_03(at)mail(dot)ru