Тезис Черча и его значимость. Элементарные шаги. Вычисления с помощью современных вычислительных машин

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

1. Тезис Черча и его значимость. Элементарные шаги

Тезис Черча важен для приложений математики в естествознание. При этом необходимо отметить, что тезис Черча не является математическим утверждением, так как в его формулировку входит понятие алгоритма в интуитивном смысле этого слова.

Тезис Черча: всякая эффективно вычислимая функция является вычислимой по Тьюрингу. Другими словами, для всякой функции, которую можно каким-либо способом вычислить, можно построить вычисляющую ее машину Тьюринга. Это утверждение, называемое обычно тезисом Черча - Тьюринга, впервые было высказано А. Тьюрингом в 1936 г. применительно к конструкции машины. Аналогичное утверждение применительно к некоторому совсем другому уточнению того же интуитивного понятия было несколько раньше высказано А. Черчем.

По своему статусу этот тезис похож скорее на законы физики, представляющие собой обычно утверждения о том, что то или иное явление природы описывается некоторой математической конструкцией (например, дифференциальным уравнением) - с той разницей, что речь идет не о явлении природы, а об одном из видов человеческой деятельности - вычислении. В справедливости физических законов мы убеждаемся путем анализа опытных данных; аналогичным образом к убеждению в справедливости тезиса Черча-Тьюринга приводит нас анализ фактов, относящихся к вычислительной практике и смежным с ней областям.

Обратимся, прежде всего, к вычислению, выполняемому человеком без использования вспомогательных средств. Слово "вычисление" следует понимать в широком смысле - не обязательно как оперирование с числами. Примерами "нечисловых вычислений" могут служить тождественные преобразования в элементарной алгебре или в логике предложений, нахождение производных от элементарных функций и т.п. Каждое вычисление состоит в последовательном преобразовании некоторого комплекса символов, записанных на бумаге или на доске. Принципиально ничего не изменится, если мы будем представлять себе, что всякое вычисление производится на одной достаточно большой доске (доска отличается от бумаги тем, что написанное на ней можно стирать и на освободившемся месте писать снова) и что доска разграфлена на клетки, причем в каждой клетке можно записать только один символ. Вычисление можно теперь рассматривать как последовательность шагов, на каждом из которых изменяется содержимое одной клетки; в общем случае это означает, что записанный в клетке символ стирается и на его месте записывается другой. Но от чего зависит, в какой клетке производится очередной шаг и что в ней на этом шаге записывается? Разумеется, не только от того, что было раньше записано в ней самой, но и от содержимого других клеток; например, при сложении "столбиком" записываемая в клетке цифра определяется цифрами, стоящими над ней. Следовательно, прежде чем изменить содержимое какой-либо клетки, нужно, вообще говоря, просмотреть некоторые другие клетки и запомнить какие-то сведения о том, что в них находится. Кроме того, следующий шаг может зависеть от предыдущих; поэтому после выполнения очередного шага бывает нужно что-то о нем запомнить.

Мы можем сказать теперь, что кроме "явных" шагов, на которых изменяется содержимое клеток, имеются еще "неявные", состоящие в просмотре клеток без изменения их содержимого. Но между этими двумя типами шагов нет принципиальной разницы, так как просмотр клетки можно представлять себе как "нулевое изменение": записываемый в клетке символ совпадает с находившимся там ранее. Таким образом, вычисление состоит из "элементарных шагов", на каждом из которых изменяется содержимое какой-то клетки, и о всяком шаге вычислитель должен, вообще говоря, что-то запомнить. В любой момент он держит в памяти какие-то сведения об уже выполненной части вычисления. После очередного шага к этим сведениям что-то добавляется и вместе с тем что-то из имевшихся ранее сведений может быть на данном шаге "использовано до конца" и за ненужностью забыто; естественно сказать, что при каждом шаге "состояние памяти" изменяется. Это "состояние памяти" можно представлять себе как набор сведений о некоторых уже выполненных шагах, причем для каждого шага указываются, скажем, координаты клетки, где он выполняется, характер изменения содержимого и "давность" этого шага по отношению к настоящему моменту. Все эти или любые другие сведения о выполненных шагах можно записать в виде некоторого слова в конечном алфавите (для данного вычисления фиксированном). Но объем памяти человека ограничен: существует константа (сейчас нам неважно, какая), ограничивающая сверху длины запоминаемых слов. Поэтому число возможных "состояний памяти" конечно.

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

Итак, мы расчленили процесс вычисления на "элементарные шаги", каждый из которых состоит в том, что "вычислитель", обозревая некоторую клетку и учитывая, каково состояние его памяти и что записано в обозреваемой клетке, производит три операции:

1) заменяет символ, записанный в обозреваемой клетке, другим символом;

2) переходит к обозрению одной из четырех соседних клеток или продолжает обозревать ту же клетку;

3) изменяет состояние памяти. Такой шаг может быть выполнен часто механически, без понимания его смысла, если имеется инструкция - при таком-то состоянии памяти и таком-то символе в обозреваемой клетке заменить этот символ на такой-то, сдвинуться в такую-то сторону (или не сдвигаться) и заменить состояние памяти на такое-то. Эта инструкция может быть, очевидно, записана в точно такой же форме, в какой записываются команды машины Тьюринга:

qa --> a'Cq',

где q и q' - состояния памяти, а' - символы, используемые при вычислении, С - принимает одно из значений "вправо", "влево", "вверх", "вниз", "на месте".

Итак, анализ процесса вычисления приводит к "двумерной машине Тьюринга", отличающейся от рассмотренной одномерной только тем, что лента заменена разграфленной на клетки доской и головка движется не в двух, а в четырех направлениях. Такая двумерная машина вполне могла бы использоваться в качестве уточнения понятия алгоритма. Но одномерная машина "технически проще" и поэтому удобнее для формальной трактовки (т.е. для доказательства теорем и т.п.), хотя принципиальной разницы между одномерным и двумерным вариантами нет (клетки, на которые разграфлена доска, можно тем или иным регулярным способом расположить на одномерной ленте). При этом, клетки, соседние на доске, не обязательно будут соседними на ленте, но всегда можно "найти" на ленте клетку, которая на доске была рядом с обозреваемой, с помощью некоторой "стандартной подпрограммы".

Таким образом, анализ того, как вычисляет человек, подтверждает тезис Черча. Применение вспомогательных средств (например, таблиц) или механических приспособлений (счеты, арифмометр) не дает ничего принципиально нового: использование таблиц всего лишь увеличивает объем памяти вычислителя (что может быть очень важно практически, но теоретического значения не имеет), а вычисления с помощью простых механизмов можно "моделировать" последовательными изменениями их (механизмов) схем, выполненных с помощью символов на клетчатой доске.

2. Вычисления с помощью современных вычислительных машин

тьюринг черч тождественный нечисловой

Что касается вычислений с помощью современных вычислительных машин с программным управлением, то и их принципиальные возможности, как известно, не превышают возможностей человека-вычислителя (единственное их преимущество - быстродействие). Кроме того, читатель, хотя бы немного знакомый с этими машинами, наверняка сразу заметил, что машины Тьюринга очень на них похожи, и построение машин Тьюринга для вычисления конкретных функций - это, в сущности, программирование (в отличие от программы для ЭВМ программа машины Тьюринга считается частью самой машины, но это вопрос терминологии). Главное отличие машин Тьюринга от реальных ЭВМ (если отвлечься от ограниченности объема памяти и времени работы последних) - крайняя простота элементарных шагов; эта простота позволяет легко строить "трансляторы" с языков реальных машин на язык машины Тьюринга. Можно сказать даже, что машина Тьюринга - это общая абстрактная схема вычислительной машины с программным управлением (но стоит подчеркнуть, что Тьюринг придумал свои машины за несколько лет до появления первых ЭВМ).

Подытоживая все изложенное, можно сказать, что анализ строения реальных вычислительных процедур убеждает нас в возможности указать для каждой такой процедуры осуществляющую ее машину Тьюринга. Это и есть главный довод в пользу тезиса Черча; к нему можно добавить еще два косвенных довода:

1) для уточнения понятия алгоритма предложено довольно много конструкций, основанных на различных соображениях и весьма разнообразных по форме; нередко в двух таких конструкциях трудно на первый взгляд усмотреть что-либо общее. Однако все эти конструкции равносильны между собой в том смысле, что всякая функция, вычислимая с помощью какой-либо одной из них, вычислима и с помощью любой другой. (При этом для каждой пары конструкций их равносильность удается строго доказать.) Никто еще не смог предложить конструкцию, приводящую к более широкому классу вычислимых функций;

2) до сих пор во всех случаях, когда для какой-либо конкретной функции, вычислимость которой в интуитивном смысле не вызывает сомнений, исследовался вопрос, вычислима ли она также и в смысле какого-либо уточнения понятия алгоритма (а значит, и всех известных уточнений), на этот вопрос удавалось получить положительный ответ.

Тезисом Черча часто пользуются для сокращения доказательств теорем теории алгоритмов: если по ходу рассуждения нужно установить, что некоторая функция вычислима по Тьюрингу, довольствуются указанием "неформальной" вычислительной процедуры и построение машины Тьюринга опускают.

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

Размещено на Allbest.ru