Машина Тьюринга и рекурсивные функции: Учебное пособие для вузов. Кто придумал тест Тьюринга? Вопросы теста Тьюринга Тьюринга edu index php t

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

Решение задачи по составлению программы для компьютера для того, чтобы он прошел этот тест, требует большого объема работы. Запрограммированный таким образом компьютер должен обладать перечисленными ниже возможностями:

• Средства обработки текстов на естественных языках (Natural Language Processing - NLP), позволяющие успешно общаться с компьютером, скажем на английском языке.
• Средства представления знаний , с помощью которых компьютер может записать в память то, что он узнает или прочитает.
• Средства автоматического формирования логических выводов , обеспечивающие возможность использовать хранимую информацию для поиска ответов на вопросы и вывода новых заключений.
• Средства машинного обучения , которые позволяют приспосабливаться к новым обстоятельствам, а также обнаруживать и экстраполировать признаки стандартных ситуаций.

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

• Машинное зрение для восприятия объектов.
• Средства робототехники для манипулирования объектами и перемещения в пространстве.

Шесть направлений исследований, перечисленных в данном разделе, составляют основную часть искусственного интеллекта, а Тьюринг заслуживает нашей благодарности за то, что предложил такой тест, который не потерял своей значимости и через 50 лет. Тем не менее исследователи искусственного интеллекта практически не занимаются решением задачи прохождения теста Тьюринга, считая, что гораздо важнее изучить основополагающие принципы интеллекта, чем продублировать одного из носителей естественного интеллекта. В частности, проблему "искусственного полета" удалось успешно решить лишь после того, как братья Райт и другие исследователи перестали имитировать птиц и приступили к изучению аэродинамики. В научных и технических работах по воздухоплаванию цель этой области знаний не определяется как "создание машин, которые в своем полете настолько напоминают голубей, что даже могут обмануть настоящих птиц".

Наверное, сегодня не такого человека, который хотя бы раз не слышал о таком понятии, как тест Алана Тьюринга. Вероятно, большинство, в общем, далеко от понимания, что собой представляет такая система тестирования. Потому остановимся на ней несколько подробнее.

Что такое тест Тьюринга: основная концепция

Еще в конце 40-х годов прошлого столетия очень многие ученые умы занимались проблемами первых компьютерных разработок. Именно тогда один из членов некой негосударственной группы Ratio Club, занимавшейся исследованиями в области кибернетики, задался совершенно логичным вопросом: можно ли создать машину, которая бы думала, как человек, или, по крайней мере, имитировала его поведение?

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

История создания

Вообще, если рассматривать тест Тьюринга как некую эмпирическую систему определения «человеческих» возможностей компьютера, стоит сказать, что косвенной основой для его создания послужили любопытные высказывания философа Альфреда Айера, которые он сформулировал еще в 1936 году.

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

В принципе, так оно и есть. Для создания мыслящей машины одной имитации мало. Очень многие ученые в качестве примера приводят братьев Райт, которые построили первый самолет, отказавшись от тенденции имитировать птиц, которая, кстати сказать, была свойственна еще такому гению, как Леонардо да Винчи.

Истрия умалчивает, знал ли сам (1912-1954) об этих постулатах, тем не менее в 1950 году он составил целую систему вопросов, которая могла бы определить степень «очеловеченности» машины. И надо сказать, эта разработка и сейчас является одной из основополагающих, правда, уже при тестировании, например, компьютерных ботов и т. д. В реальности же принцип оказался таковы, что пройти тест Тьюринга удалось лишь нескольким программам. И то, «пройти» - сказано с большой натяжкой, поскольку результат тестирования никогда не имел показателя 100 процентов, в лучшем случае - чуть более 50.

В самом же начале своих исследований ученый использовал собственное изобретение. Оно получило название «тест-машина Тьюринга». Поскольку все беседы предполагалось ввести исключительно в печатном виде, ученый задал несколько основных директив по написанию ответов, таких как перемещение печатной ленты влево или вправо, печать определенного символа и т. д.

Программы ELIZA и PARRY

Со временем программы стали усложняться, а две из них в ситуациях, когда применялся тест Тьюринга, показали ошеломляющие на то время результаты. Таковыми стали ELIZA и PARRY.

Что касается «Элизы», созданной в 1960 году: исходя из вопроса, машина должна была определить ключевое слово и на его основе составить обратный ответ. Именно это позволяло обманывать реальных людей. Если такого слова не оказывалось, машина возвращала обобщенный ответ или повторяла один из предыдущих. Однако прохождение теста «Элизой» до сих пор остается под сомнением, поскольку реальных людей, которые общались с программой, изначально подготавливали психологически таким образом, чтобы они заранее думали, что разговаривают с человеком, а не с машиной.

Программа PARRY несколько похожа на «Элизу», но была создана для имитации общения параноика. Что самое интересное, для ее тестирования были использованы настоящие пациенты клиник. После записи стенограмм бесед в режиме телетайпа их оценивали профессиональные психиатры. Лишь в 48 процентах случаев они смогли правильно оценить, где человек, а где машина.

Кроме того, практически все тогдашние программы работали с учетом определенного промежутка времени, поскольку человек в те времена соображал намного быстрее машины. Сейчас - наоборот.

Суперкомпьютеры Deep Blue и Watson

Достаточно интересными выглядели разработки корпорации IBM, которые не то чтобы мыслили, но обладали невероятной вычислительной мощностью.

Наверное, многие помнят, как в 1997 году суперкомпьютер Deep Blue выиграл 6 партий в шахматы у тогдашнего действующего чемпиона мира Гарри Каспарова. Собственно, тест Тьюринга применим к этой машине весьма условно. Все дело в том, что в нее изначально было заложено множество шаблонов партий с невероятным количеством интерпретации развития событий. Машина могла оценивать порядка 200 миллионов позиций фигур на доске в секунду!

Компьютер Watson, состоявший из 360 процессоров и 90 серверов, выиграл американскую телевикторину, обойдя по всем параметрам двух других участников, за что, собственно, и получил 1 миллион долларов премии. Опять же, вопрос спорный, поскольку в машину были заложены невероятные объемы энциклопедических данных, а машина просто анализировала вопрос на предмет наличия ключевого слова, синонимов или обобщенных совпадений, после чего давала правильный ответ.

Эмулятор Eugene Goostman

Одним из самых интересных событий в этой области стала программа одессита Евгения Густмана и российского инженера Владимира Веселова, ныне проживающего в США, которая имитировала личность 13-летнего мальчика.

7 июня 2014 года программа Eugene показала свои возможности в полном объеме. Интересно, что в тестировании приняли участие 5 ботов и 30 реальных людей. Только в 33% случаев из ста жюри смогло определить, что это компьютер. Дело тут в том, что задача осложнялась тем, что у ребенка интеллект ниже, чем у взрослого человека, да и знаний поменьше.

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

Тем не менее это все-таки эмулятор, а не мыслящее существо. Так что восстание машин не состоится еще очень долго.

Обратная сторона медали

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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Т.К. Кацаран, Л.Н. Строева МАШИНА ТЬЮРИНГА И РЕКУРСИВНЫЕ ФУНКЦИИ Учебное пособие для вузов Издательско-полиграфический центр Воронежского государственного университета 2008 Утверждено научно-методическим советом факультета ПММ 25 мая 2008 г., протокол № 9 Рецензент д. т. н., проф. кафедры математических методов исследования операций Т.М. Леденева Учебное пособие подготовлено на кафедре нелинейных колебаний факуль- тета ПММ Воронежского государственного университета. Рекомендуется для студентов 1 курса факультета ПММ ВГУ, Староосколь- ского и Лискинского филиалов ВГУ. Для специальности 010500 – Прикладная математика и информатика ВВЕДЕНИЕ Слово «алгоритм» происходит от algorithmi – латинского написания имени узбекского математика и астронома, жившего в VIII–IX веках (783– 850 гг.), Мухаммеда бен Мусы аль-Хорезми. Под этим именем в Средневе- ковой Европе знали величайшего математика из Хорезма (город в совре- менном Узбекистане). В своей книге «Об индийском счете» он сформули- ровал правила записи натуральных чисел с помощью арабских цифр и пра- вила действий над ними. Затем понятие алгоритма стало использоваться в более широком смысле и не только в математике. Как для математиков, так и для практиков понятие алгоритма имеет важное значение. Таким образом, можно сказать, что алгоритм – это точное предписа- ние о выполнении в определенном порядке некоторой системы операций для решения всех задач одного и того же типа, определяющее последова- тельность действий, обеспечивающую получение требуемого результата из исходных данных. Заметим, что это не определение понятия «алгоритм», а только его описание, его интуитивный смысл. Алгоритм может быть предназначен для выполнения его как челове- ком, так и автоматическим устройством. Данное представление об алгоритме не является строгим с матема- тической точки зрения, так как в нем используются такие понятия как «точное предписание» и «исходные данные», которые, вообще говоря, строго не определены. Особенностью любого алгоритма является его способность решать некоторый класс задач. Например, это может быть алгоритм решения сис- тем линейных уравнений, нахождение кратчайшего пути в графе и т. д. Создание алгоритма, пусть даже самого простого, – процесс твор- ческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеюще- 3 гося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в сущность дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная маши- на-автомат, которая неукоснительно исполняет предписанные ей дейст- вия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь фор- мальными исполнителями являются различные автоматические устрой- ства, и компьютер в том числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совер- шать исполнитель, называются его допустимыми действиями. Совокуп- ность допустимых действий образует систему команд исполнителя. Ал- горитм должен содержать только те действия, которые допустимы для данного исполнителя. Поэтому обычно формулируют несколько общих свойств алгорит- мов, позволяющих отличать алгоритмы от других инструкций. Алгоритм должен обладать следующими свойствами. Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмот- ренное алгоритмом, исполняется только после того, как закончилось ис- полнение предыдущего. Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойст- ву выполнение алгоритма носит механический характер и не требует ника- ких дополнительных указаний или сведений о решаемой задаче. Результативность (конечность) – алгоритм должен приводить к ре- шению задачи за конечное число шагов. 4 Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, раз- личающихся только исходными данными. При этом исходные данные мо- гут выбираться из некоторой области, которая называется областью при- менимости алгоритма. Теория алгоритмов – это раздел математики, который изучает общие свойства алгоритмов. Различают качественную и метрическую теорию ал- горитмов. Основной проблемой качественной теории алгоритмов является про- блема построения алгоритма, обладающего заданными свойствами. Такую проблему называют алгоритмической. Метрическая теория алгоритмов исследует алгоритм с точки зрения их сложности. Этот раздел теории алгоритмов известен также как алго- ритмическая теория сложности. При отыскании решений некоторых задач долго не удавалось най- ти соответствующий алгоритм. Примерами таких задач являются: а) ука- зать способ, согласно которому для любой предикатной формулы за ко- нечное число действий можно выяснить, является ли она тождественно- истинной или нет; б) разрешимо ли в целых числах диофантово уравне- ние (алгебраическое уравнение с целыми коэффициентами). Так как для решения этих задач найти алгоритмов не удалось, возникло предполо- жение, что такие алгоритмы вообще не существуют, что и доказано: первая задача решена А. Черчем, а вторая – Ю.В. Матиясевичем и Г.В. Чудновским. Доказать это с помощью интуитивного понятия алго- ритма в принципе невозможно. Поэтому были предприняты попытки дать точное математическое определение понятия алгоритма. В середине 30-х годов ХХ века С.К. Клини, А.А. Марков, Э. Пост, А. Тьюринг, А. Черч и другие предположили различные математические определения 5 понятия алгоритма. Впоследствии было доказано, что эти различные формальные математические определения в некотором смысле эквива- ленты: вычисляют одно и то же множество функций. Это говорит о том, что, по-видимому, основные черты интуитивного понятия алгоритма правильно отражены в этих определениях. Далее рассмотрим математическое уточнение алгоритма, предло- женное А. Тьюрингом, которое называют машиной Тьюринга. 6 1. МАШИНА ТЬЮРИНГА § 1. Математическая модель машины Тьюринга Идея создания машины Тьюринга, предложенная английским мате- матиком А. Тьюрингом в тридцатых годах XX века, связана с его попыт- кой дать точное математическое определение понятия алгоритма. Машина Тьюринга (МТ) – это математическая модель идеализиро- ванной цифровой вычислительной машины. Машина Тьюринга является таким же математическим объектом, как функция, производная, интеграл, группа и т. д. Так же как и другие мате- матические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Для описания алгоритма МТ удобно представлять некоторое устрой- ство, состоящее из четырех частей: ленты, считывающей головки, устрой- ства управления и внутренней памяти. 1. Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клет- ке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты зану- мерованы 1, 2, 3, … . В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан толь- ко один символ (буква) из внешнего алфавита A = {L, a1 , a 2 ,..., a n -1 }, n ³ 2 . Пустая ячейка обозначается символом L, а сам символ L называется пустым, при этом остальные символы называются непустыми. В этом ал- фавите A в виде слова (конечного упорядоченного набора символов) ко- дируется та информация, которая подается в МТ. Машина «перерабатыва- ет» информацию, поданную в виде слова, в новое слово. 2. Считывающая головка (некоторый считывающий элемент) пере- мещается вдоль ленты так, что в каждый момент времени она обозревает 7 ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оста- ваться на месте (Н). Обозначим множество перемещений (сдвига) головки D = {П, Л, Н}. Если в данный момент времени t головка находится в край- ней клетке и сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка, над которой окажется головка в момент t + 1 . 3. Внутренняя память машины представляет собой некоторое конеч- ное множество внутренних состояний Q = { q0 , q1 , q 2 , ..., q m }, m ³ 1 . Бу- дем считать, что мощность |Q | ³ 2. Два состояния машины имеют особое значение: q1 – начальное внутреннее состояние (начальных внутренних состояний может быть несколько), q0 – заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоя- нием. Например, под ячейкой, над которой находится головка, указывается внутреннее состояние машины. ¯ a2 a1 L a2 a3 q1 4. Устройство управления в каждый момент t в зависимости от счи- тываемого в этот момент символа на ленте и внутреннего состояния ма- шины выполняет следующие действия: 1) изменяет считываемый в момент t символ ai на новый символ a j (в частности оставляет его без изменений, т. е. ai = a j); 2) передвигает головку в одном из следующих направлений: Н, Л, П; 3) изменяет имеющееся в момент t внутреннее состояние машины 8 qi на новое q j , в котором будет машина в момент времени t +1 (может быть, что qi = q j). Такие действия устройства управления называют командой, которую можно записать в виде: qi ai ® a j D q j , (1) где qi – внутреннее состояние машины в данный момент; a i – считываемый в этот момент символ; a j – символ, на который изменяется символ a i (может быть ai = a j); символ D есть или Н, или Л, или П и указывает направление движения головки; q j – внутреннее состояние машины в следующий момент (может быть qi = q j). Выражения qi ai и a j D q j называются левой и правой частями этой команды соответственно. Число команд, в которых левые части попарно различ- ны, является конечным числом, так как множества Q \ {q 0 } и A конечны. Не существует команд с одинаковыми левыми частями, т. е. если про- грамма машины T содержит выражения qi ai ® a j D q j и qt at ® ak D qk , то qi ¹ qt или ai ¹ at и D О {П, Л, Н } . Совокупность всех команд называется программой машины Тьюринга. Максимальное число команд в программе равно (n + 1) Ч m , где n + 1 = A и m + 1 = Q . Считается, что заключительное состояние команды q0 может стоять только в правой части команды, начальное состояние q1 может стоять как в левой так и в правой части команды. Выполнение одной команды называется шагом. Вычисление (или ра- бота) машины Тьюринга является последовательностью шагов одного за другим без пропусков, начиная с первого. Итак, МТ задана, если известны четыре конечных множества: внешний алфавит A , внутренний алфавит Q , множество D перемещений головки и программа машины, представляющая собой конечное множество команд. 9 § 2. Работа машины Тьюринга Работа машины полностью определяется заданием в первый (на- чальный) момент: 1) слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); 2) положения головки; 3) внутреннего со- стояния машины. Совокупность этих трех условий (в данный момент) на- зывается конфигурацией (в данный момент). Обычно в начальный момент внутренним состоянием машины является q1 , а головка находится либо над первой слева, либо над первой справа клеткой ленты. Заданное слово на ленте с начальным состоянием q1 и положение головки над первым словом называется начальной конфигурацией. В про- тивном случае говорят, что машина Тьюринга не применима к слову на- чальной конфигурации. Другими словами, в начальный момент конфигурация представима в следующем виде: на ленте, состоящей из некоторого числа клеток, в каж- дой клетке записан один из символов внешнего алфавита A , головка нахо- дится над первой слева или первой справа клеткой ленты и внутренним со- стоянием машины является q1 . Получившееся в результате реализации этой команды слово на ленте и положение головки называется заключи- тельной конфигурацией. Например, если в начальный момент на ленте записано слово a1La 2 a1a1 , то начальная конфигурация будет иметь вид: a1 a2 L a1 a1 q1 (под клеткой, над которой находится головка, указывается внутреннее со- стояние машины). 10

We see it all the time. “RESTful” this, “REST” protocol that, etc. However, a lot of us don’t really understand exactly what it means. We’ll fix exactly that gap in this article!

State

In computer science (and mathematics, to some extent), there is a concept of state. A certain system can be in state A or it can be in state B or it can be a bunch of other states (usually, a finite list of states).

As an example, let us say that you write a program which turns the screen red if the temperature is more than 80 degreees farenheit or turns it blue if the temperature is less than 80 degrees farenheit.

We can call the first state (temp > 80 degrees) state “A” and the second state (temp < 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

That is the general idea of state. Here’s the definition given by the all-knowing Wikipedia:

“In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given point in time, which is used by the circuit or program.”

In short, it is a sort of “combination” of all the information that the program takes into account.

Now, we’re going to make a leap into something that’s considered largely theoretical and useless and then somehow connect to the very practical world of REST.

Turing machines

There was this man named Alan Turing, and he was quite a smart mathematician with an interest in the workings of computers. He conceived an imaginary computer (which, as we will see, is actually impossible to actually build) which he used to reason about things that happen in real computers.

The computer consists of a tape of infinite length, with a head through which the tape passes. The tape has “cells”, to which information can be written (numbers, colors, etc.) The tape moves through this machine, left or right, one cell at a time. The machine scans in whatever is already on the tape and, depending on what state it is in, it writes something back onto the tape then, subsequently, changes its state.

You may want to read that definition again for it to sink in completely. The essence of the idea is that it makes operations on memory based on state and states changes according to operations on memory.

This seems like a fairly useless theoretical fantasy (although, there is absolutely nothing wrong with that, read A Mathematician’s Apology if you’re wondering why people care to take an interest in theoretical stuff). However, it is quite possibly the most fundamental concept of computer science.

Using the Turing Machine, computer scientists are able to reason about any algorithm that can be run on a computer. In fact, the Turing machine has led to many advances in computer science.

So, the Turing Machine shows us that today (note: I’m not considering graph reduction processors), literally everything in computer science is based off the idea of state.

The Network

Then came along the concept of the internet. This is a place where packets can go haywire and are resent until they reach their destination. In general, there is never a complete transmission of full data.

Clients come in quickly and leave twice as fast. As such, holding onto client state doesn’t make much sense when working on a network system.

Also, in general, holding too much state in a system has been a cause for major pain (which also leads to funcitonal programming languages, which do not allow for the holding of state in a large portion of your code).

Now, people needed a network protocol for the internet which was simple, fast and handled management of state well in an extremely dynamic environment.

That protocol was HTTP, and the theory that grew out of the work on HTTP was labelled REST.

REST

REST stands for: REpresentational State Transfer. It is a system built around the “client-server” concept that networks are built on top of (well, ther are also peer to peer type networks, but, client-sever is arguably the simplest and most tested architecture). The name itself is slightly misleading, since the server is completely state-free!

There are a few constraints that all systems that claim to be “RESTful” must follow.

First of all, it must be a client-server system. This constraint has been modified in the past, but in the formal definition (and, for the theory of REST to work properly), we have servers to which clients can connect.

The server is fully stateless. This means that for each client request to the server, no state is reserved on the server. For example, if a client (using HTTP), requests the index page and subsequently requests the /user/home page, the two requests are completely independent of each other. The client holds all of the state of the system (hence, we have the back button).

Responses from the server must be cacheable, which means that there must be a system on the server which identifies respones as cacheable or not, so that clients (e.g. web browsers) can take advantage of the cache.

Finally, we must have a simple, clean, and uniform interface. If you have had some experience with how HTTP works, the request forms are very simple. They are largely verbs and nouns with a very easy to parse and human-readable format. SOAP is another form of a network protocol which absolutely obliterates this requirement and, therefore, is often very difficult to work with.

Now, what do all of these properties, when taking together, entail?

Implications of REST

They let us build systems that are cleanly seperated, scalable, and debugged easily.

Let us consider the restriction of statelessness on the server first, it may well be the most important (and, also, the most often violated by so-called RESTful architectures) bit.

As previously mentioned, in a client-server architecture the clients are very nimble; they fire requests and suddenly kill all communication. In this kind of a situation, it is much cleaner to not save state about the client on the server. This lets us reason about HTTP servers very easily; each client request may be treated as if it is a completely new client, and it wouldn’t make a penny of a difference.

Secondly, cacheable responses mean that the clients are able to get data much faster, because often times, the data can be retrieved from the client’s memory. This immediately increases client performance and, in some systems, server scalability.

The uniform interface may just be the most important. Having worked with SOAP, I can tell you that HTTP’s simple format is a blessing when trying to debug server code and the same applies to other RESTful systems.

Designing a RESTful System

Let’s say we need to write a server that returns stock quotes, as well as retaining a list of stock quotes to monitor (and, the user can either add to or clear the list).

This is an excellent case for a RESTful system, because it is inherently independent of identity of client. Therefore, the server need not hold any state about the client.

We first start by defining how the protocol language will work (a bit like the GET and POST verbs of HTTP):

GETQUOTE ticker - gives the price for a particular stock
ADDTICKER ticker - adds the given stock to the list
GETLIST - gets a comma seperated list of stocks in the list

That’s a fairly simple protocol, and, doesn’t hold any state on the server. Now, as for caching, we may say that we update the prices every hour, so caches more than one hour old may be thrown away.

And, that’s all there is to it! Of course, we still have to implement this, but, the general idea of the system is quite simple and clean!

Conclusion

Hopefully, this article gave you a solid understanding of REST.

Also, I hope that you will now be able to call out people who throw around the term “RESTful” too much - I can tell you, there’s a lot of them!

ТЬЮРИНГ

ТЬЮРИНГ (Turing) Алан (1912-54), английский математик и логик, который сформулировал теории, ставшие впоследствии основой компьютерной техники. В 1937 г. придумал машину Тьюринга - гипотетическую машину, способную преобразовывать набор вводимых команд. Она была предвестницей современных компьютеров. Тьюринг также использовал идею компьютера, чтобы дать альтернативное и более простое доказательство теоремы ГЕДЕЛЯ о неполноте. Тьюринг сыграл основную роль в разгадке «Энигмы» (Enigma) - комплексного метода шифрования, который использовала Германия во время Второй мировой войны. В 1948 г. участвовал в создании одного из первых в мире компьютеров. В 1950 г. придумал тест Тьюринга - предполагалось, что это тест на способность компьютера «мыслить». По существу в нем утверждалось, что человек не сможет отличить диалог с машиной от диалога с другим человеком. Это работа проложила путь к созданию ИСКУССТВЕННОГО ИНТЕЛЛЕКТА. Тьюринг также занимался теоретической биологией. В работе «Химическая основа морфогенеза» (1952) он предложил модель, описывающую происхождение различных схем строения организмов в биологии. С тех пор такие модели часто применяются для описания и объяснения многих систем, наблюдаемых в природе. Тьюринг покончил с собой, будучи официально обвинен в гомосексуализме.

Научно-технический энциклопедический словарь .

Смотреть что такое "ТЬЮРИНГ" в других словарях:

Тьюринг, Алан Матисон Алан Тьюринг Alan Mathison Turing Памятник в Сэквиль Парке Дата рождения … Википедия

- (Turing) Алан Матисон (1912 54), английский математик. В 1936 1937 ввел математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название машина Тьюринга … Современная энциклопедия

- (Turing), Алан Матисон (23 июня 1912 – 7 июня 1954) – англ. логик и математик. В 1936–37 предложил идеализированную машинную модель вычислит. процесса – вычислительную схему, близкую к действиям человека, производящего вычисления, и выдвинул… … Философская энциклопедия

Тьюринг А. - Тьюринг А. Английский математик. Тематики защита информации EN Turing … Справочник технического переводчика

Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 … Википедия

Тьюринг - английский математик Алан М.Тьюринг, один из создателей логических основ вычислительной техники, в частности, дал одно из формальных определений алгоритма; доказал, что существует класс вычислительных машин, которые могут имитировать… … Мир Лема - словарь и путеводитель

- (Turing) Алан Матисон (23.6.1912, Лондон, 7.6.1954, Уилмслоу, близ Манчестера), английский математик. Член Королевского общества (1951). По окончании Кембриджского университета (1935) работал над докторской диссертацией в Принстонском… … Большая советская энциклопедия

Тьюринг А. М. - ТЬЮ́РИНГ (Turing) Алан Матисон (1912–54), англ. математик. Осн. тр. по матем. логике, вычислит. математике. В 1936–37 ввёл матем. понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем назв. машина Т … Биографический словарь

- (полн. Алан Матисон Тьюринг, Alan Mathison Turing) (23 июня 1912, Лондон 7 июня 1954, Уилмслоу, Великобритания), британский математик, автор трудов по математической логике, вычислительной математике. В 1936 1937 годах ввел математическое понятие … Энциклопедический словарь

Книги

• Может ли машина мыслить? Общая и логическая теория автоматов. Выпуск 14 , Тьюринг А. , Настоящая книга, содержащая работы Алана Тьюринга и Джона фон Неймана, стоявших у истоков создания первых&171;мыслящих машин&187;ЭВМ, относится к классике философско-кибернетического… Категория: Базы данных Серия: Науки об искусственном Издатель: URSS , Производитель: URSS ,
• Может ли машина мыслить? Общая и логическая теория автоматов. Выпуск № 14 , Тьюринг А. , Настоящая книга, содержащая работы Алана Тьюринга и Джона фон Неймана, стоявших у истоков создания первых «мыслящих машин» ЭВМ, относится к классике философско-кибернетического направления… Категория: