2015-04-01
914
Алгоритм, составленный с использованием многократных повторений одних и тех же действий, называется циклическим. Все циклические конструкции делятся на три основных типа: цикл с предусловием, цикл с постусловием, цикл со счётчиком. Например: заданы N точек на плоскости (xi, yi), i = 1,2,.. N. Найти длину соответствующей ломаной. Для реализации алгоритма решения такой задачи потребуется использовать цикл со счётчиком.
Понятие алгоритма, которое приводилось выше, имеет интуитивный, нестрогий характер. Интерес к алгоритмам возрос в связи с проблемами Давида Гильберта, которые он сформулировал в 1900 г. на Парижском конгрессе математиков. Одна из этих проблем заключалась в отыскании универсальной процедуры для решения математических задач или в ответе на вопрос о принципиальной возможности такой процедуры.
Пусть А - посылка, В - следствие. Для любых А, В требуется узнать, существует ли дедукция, с помощью которой можно вывести В из А? Решением этой проблемы занимались многие математики и логики. Алан Тьюринг был одним из них. В 1928 г. Гильберт поставил задачу построения математики на незыблемом фундаменте из аксиом и правил вывода (логики), установленных раз и навсегда.
|
|
|
Сразу отметим, что все усилия, направленные на решение этой задачи были перечёркнуты великим открытием, которое сделал Курт Гёдель в 1931 г. Он доказал, что для любой полной и непротиворечивой аксиоматической системы можно сформулировать такие утверждения, которые не выводимы в ней (их нельзя ни доказать, ни опровергнуть в рамках таких систем). И даже проблема непротиворечивости системы аксиом, будучи сформулированной в виде теоремы, сама является недоказуемой в рамках такой системы. Примером такой аксиоматической теории является геометрия Евклида и проблема пятого постулата[4] о параллельных прямых. Эта проблема была снята после создания Н.И. Лобачевским в 1826 г. непротиворечивой геометрии, в которой отрицался пятый постулат.
Концепция универсального вычислительного устройства, известного как машина Тьюринга (МТ), была предложена в 1935-1936 годах математиком Аланом Тьюрингом как средство алгоритмического решения проблемы Д. Гильберта: существует ли универсальная механическая процедура позволяющая, в принципе, решить все математические задачи? Работая над этой проблемой, Тьюринг создал некоторую идеализацию машины, выполняющей «механические процедуры». Следует подчеркнуть, что реально МТ не существует - это лишь идеальный (математический) объект.
МТ - это устройство, которое может принимать конечное, хотя, может быть, и очень большое число внутренних состояний, которое способно работать со сколь угодно большим объёмом данных. Эти данные располагаются на внешнем носителе, в качестве которого Тьюринг рассматривал бесконечную ленту, разбитую на отдельные «ячейки», в каждой из которых может храниться один символ. МТ имеет устройство (считывающую головку), которое может считывать символ из отдельной ячейки ленты и продвигать её влево и вправо относительно считывающей головки.
|
|
|
Обозначим через А={a0, a1, a2, a3,... an} – алфавит МТ, Q= { q0, q1, q2, q3,... qn } – конечное множество состояний МТ. Работа МТ описывается следующим образом: если в некоторый момент времени машина находится в состоянии qn и головка МТ обозревает символ аm, то затем МТ записывает в текущую «ячейку» символ аS, затем сдвигается на одну позицию влево (L) или вправо (R) или остаётся на месте (S), после чего переходит в состояние qk. Описание работы МТ можно представить в виде: q n a m ® a s (L или R или S) q k; q1 – начальное состояние машины, q0 – конечное состояние (останов МТ), a0- символ пробела (пустая клетка).
Набор таких правил (программу) для МТ обычно представляют в виде таблицы, например:
| a0 | a1 | a2 | |
| q1 | a2 L q3 | a1 R q2 | a2 L q1 |
| q2 | a0 S q2 | a2 S q1 | a1 S q2 |
| q3 | a0 R q0 | a1 R q4 | a2 S q1 |
| q4 | a1 S q3 | a0 R q4 | a2 R q4 |
Эта машина может находиться в 5-ти состояниях – q0, q1, q2, q3, q4, а её алфавит состоит из трёх символов а0, a1 и a2. Заметим, что хотя бы одна ячейка таблицы должна содержать символ q0 – иначе МТ никогда не остановится.
Покажем, как работает эта МТ, если на входе у неё задана последовательность символов a0, a2, a2, a0, причём МТ в начальный момент обозревает второй символ справа – a2 и находится в состоянии q1.
1 шаг (исходная позиция)
| а0 | а2 | а2 | а0 |
q1
2 шаг
| а0 | а2 | а2 | а0 |
q1
3 шаг
| а0 | а2 | а2 | а0 |
q1
4 шаг
| a0 | a2 | а2 | а2 | а0 |
q3
5 шаг
| a0 | a2 | а2 | а2 | а0 |
q0 (stop)
Другой пример: пусть той же МТ предъявлена на входе последовательность символов a0, a1, a1, a2, a2, a0 и МТ обозревает второй справа символ a2 и находится в состоянии q1.
1 шаг (исходная позиция)
| a0 | a1 | a1 | а2 | a2 | a0 |
q1
2 шаг
| a0 | a1 | a1 | а2 | a2 | a0 |
q1
3 шаг
| a0 | a1 | a1 | а2 | a2 | a0 |
q1
4 шаг
| a0 | a1 | a1 | а2 | a2 | a0 |
q2
5 шаг
| a0 | a1 | a1 | а1 | a2 | a0 |
q2
6 шаг
| a0 | a1 | a1 | a2 | a2 | a0 |
q1
На 6 шаге полностью повторилась конфигурация 2 шага, т.е. произошло «зацикливание» работы МТ. Вывод: для такого исходного набора данных МТ никогда не остановится.
Устройство и работа машины Тьюринга по заданной программе удовлетворяют всем требованиям, предъявляемым к работе по заданному алгоритму. Единственное замечание – возможность «зацикливания» конкретной МТ. Именно это сходство работы МТ и выполнения некоторого алгоритма позволило сформулировать знаменитый тезис Чёрча – Тьюринга, суть которого можно выразить следующим образом: «Для любого алгоритма можно построить машину Тьюринга, которая его реализует». Этот тезис нельзя доказать, поскольку нет формального, строгого определения алгоритма. Но его можно опровергнуть, если удастся привести пример алгоритма, для которого нельзя задать реализующую его МТ. До настоящего времени таких примеров построить не удалось. Наряду с машиной Тьюринга существует аналогичное «устройство» - машина Поста. Эти машины эквивалентны в том смысле, что алгоритм, который реализуем на МТ, может быть реализован и на машине Поста. Более того, в соответствии с тезисом Чёрча-Тьюринга, работа любого компьютера может быть воспроизведена на соответствующей МТ.
В настоящее время существует три основных направления в теории алгоритмов. Первое направление представлено такими учёными как А. Чёрч, Л. Гёдель, С. Клини и связано с уточнением понятия эффективно вычислимой функции. Функция F(x1,x2,x3, ….,xn) от целочисленных аргументов x1,x2,x3, ….,xn называется эффективно вычислимой, если существует алгоритм, позволяющий вычислять её значения. Это понятие также является интуитивным, так как опирается на нестрогое понятие алгоритма. Однако опираясь на строгое математическое определение частично рекурсивных функций и тезис А.Чёрча о том, что «Класс интуитивно вычислимых функций совпадает с классом частично рекурсивных функций», можно получить строго обоснованную теорию алгоритмов.
|
|
|
Второе направление связано с рассмотрением процессов, осуществляемых в вычислительной машине, и базируется на идеях, связанных с машиной Тьюринга. Третье направление связано с понятием нормальных алгоритмов, введённым и разработанным российским математиком А.А. Марковым.
На современном этапе развития в теории алгоритмов возникли новые проблемы. В связи с появлением в программировании новых направлений: логического, функционального и объектно-ориентированного, - в теории алгоритмов, наряду с классическим «императивным» понятием алгоритма, были введены объектно-ориентированные и распределённые алгоритмы.
ООП «уравнивает» в правах алгоритмы и данные: алгоритм теперь – часть структуры данных. Развитию идеи распределённых алгоритмов способствовало тотальное расространение Интернета (WWW). Проблема данных, их представления и типа становится более серьёзной, чем проблема алгоритмов благодаря появлению суперструктуры всех файлов – WWW.
С понятием алгоритма тесно связана проблема «искусственного интеллекта». Проблемы искусственного интеллекта были поставлены задолго до появления первых ЭВМ. Однако прогресс в вычислительной технике только усилил интерес к этим проблемам. В самой общей постановке вопроса под искусственным интеллектом понимается умение имитировать различные аспекты деятельности человеческого разума. В отдельных направлениях разработки ИИ достигли впечатляющих результатов: в роботехнике, в экспертных системах, в игре в шахматы и т.д. Однако до настоящего времени полностью имитировать работу человеческого разума пока не удалось.
Алан Тьюринг предложил тест, с помощью которого можно было бы определить, что ИИ создан. Суть теста заключается в следующем: пусть имеется непроницаемый экран, за которым находится человек и компьютер. По другую сторону располагается другой человек (испытатель), который задаёт вопросы, вступает в контакт с расположенными по другую сторону экрана человеком или компьютером. Человек пытается честно убедить испытателя, что он и есть живое существо, то же самое делает и компьютер. Испытатель не знает, кто отвечает ему – человек или компьютер. Он должен «разоблачить» машину. Естественно, что ответы должны выдаваться в обезличенной форме, например, на принтере. Если в ходе такого диалога испытателю не удастся определить, кто ему отвечал - человек или компьютер, то можно утверждать, что искусственный интеллект создан.
|
|
|
В вопросе о принципиальной возможности имитации человеческого разума с помощью машин есть как сторонники, так и противники. Сторонники идеи создания искусственного интеллекта (ИИ) опираются на понятие алгоритма и на тезис Чёрча-Тьюринга. Они утверждают, что любая деятельность человеческого мозга осуществляется в соответствии с некоторым алгоритмом. Следовательно, свойства разума присущи логическим действиям любого вычислительного устройства, т.к. умственная деятельность – это просто выполнение некоторой хорошо определённой последовательности операций, т.е. некоторого алгоритма.
Разница между работой мозга и более простого устройства (термостата) состоит лишь в сложности алгоритма. Раз существует алгоритм, по которому работает мозг, то можно создать соответствующую программу и запустить её на компьютере, т.е. получить «думающую» ЭВМ. Последовательное развитие идеи ИИ приводит к признанию возможности телепортации: закодировав с помощью программы работу сознания можно затем записать её на любой носитель, передать с помощью радиосигналов на удалённое расстояние, принять и воспроизвести на подходящем устройстве (компьютере).
Одним из известных противников теории сильного ИИ является Джон Сёрль. Ему принадлежит идея мысленного эксперимента под названием «Китайская комната», в котором критикуется возможность моделирования человеческого понимания естественного языка и, в частности, критикуется тест Тьюринга. Сёрль считал, что при наличии исчерпывающего руководства по переходу от вопроса на китайском языке к ответу на этом же языке, человек способен поддерживать диалог на китайском языке, не понимая при этом по-китайски ни слова. Суть предлагаемого Сёрлем эксперимента состоит в следующем.
«Предположим, что меня поместили в комнату, в которой расставлены корзинки, полные китайских иероглифов и дали учебник на английском языке, в котором приводятся правила сочетания символов китайского языка, причём правила эти можно применять, зная лишь форму символов, понимать значение символов совсем необязательно. Представим себе, что находящиеся за дверью комнаты люди, понимающие китайский язык, передают в комнату наборы символов, и что в ответ я манипулирую символами согласно правилам и передаю обратно другие наборы символов. В данном случае книга правил есть не что иное, как «компьютерная программа». Люди, написавшие её, — «программисты», а я играю роль «компьютера». Корзинки, наполненные символами, — это «база данных»; наборы символов, передаваемых в комнату, это «вопросы»; а наборы, выходящие из комнаты, это «ответы».
Предположим далее, что книга правил написана так, что мои «ответы» на «вопросы» не отличаются от ответов человека, свободно владеющего китайским языком. Таким образом, я выдержу тест Тьюринга на понимание китайского языка. Но все же, на самом деле, я не понимаю ни слова по-китайски. Подобно компьютеру, я манипулирую символами, но не могу придать им какого бы то ни было смысла». Суть возражений Сёрля состоит в том, что правильное манипулирование символами с помощью компьютера ещё не означает, что компьютер понимает суть и смысл производимых манипуляций. В заключение отметим, что до сегодняшнего дня создать что-то, достойное называться подлинным интеллектом, пока никому не удалось.
