Она такой же математический объект, как функция,

Год Алана Тьюринга в мире и Украине Суть мероприятия Организаторы Статистика Жизненный путь Трагедия личной жизни Признание Современные экспликации теории Тьюринга Варианты интерпретации теста Критика теста Прогнозы Достижения и вклад в науку Криптография Машина Тьюринга Тест Тьюринга

Более 70 университетов мира Более 50 организаций - партнеров проекта Более 80 запланированных мероприятий Международные научные и творческие конкурсы, конкурсы на получение стипендий Экспозиции, посвященные Алану Тьюрингу и его деятельности Циклы кино- и телепоказов Издание целого ряда книг Ряд мероприятий, которые будут проводиться в течение 2012 года во множестве стран мира. Значительная часть событий будет проведена в местах, имевших особое значение в жизни Алана Тьюринга – Кембридже, Манчестере и Блетчли Парке. (The Turing Centenary, The Alan Turing Year)

(Alan Mathison Turing) 23 июня июня 1954 Великобритания Ввёл математическое понятие абстрактного эквивалента алгоритма, или вычислимой функции, получившее затем название «машины Тьюринга». Одним из первых поставил вопрос о способности вычислительной машины мыслить, то есть вопрос об искусственном интеллекте, и первым предложил критерий оценки мыслительных способностей машины. Внес вклад в криптографию, математику, логику и все дальнейшее развитие компьютерных наук. Его часто называют «отцом компьютерной науки», основоположником теории искусственного интеллекта, первым теоретиком современного программирования и даже первым в мире хакером.

Корни семьи Тьюрингов восходят к XIV веку, к старому шотландскому роду баронетов Turins of Foveran из графства Абердиншир. Дед, Джон Роберт Тьюринг: ученая степень по математике в Кембридже. Отец, Джулиус Мэтисон Тьюринг: степень бакалавра по истории и литературе в Оксфорде; изучение индийской истории и языков. Мать, Этель Сара Стоуни: изучала искусство и музыку в Сорбонне. Род Стоуни: известная в научном мире семья, давшая миру известного физика Джорджа Стоуни, члена английского Королевского общества. «Биография человека никогда не начинается с момента его рождения. Тем более биография истинного гения. Ведь для того чтобы возникла телесная и духовная структура, в которой гений проявился бы во всей своей полноте, необходимо необычайно планомерное взаимодействие, смешение генов и хромосом, неизъяснимых сил и материй к тому же на протяжении нескольких поколений» Иштван Барна

Безобразная успеваемость… Безнадежное отставание… Он принадлежит к числу тех учеников, которые создают проблемы для любой школы и всего общества Отзывы школьных учителей Алана Тьюринга Если он останется в школе, то должен поставить перед собой цель – стать образованным. Если же он должен быть только ученым, то напрасно тратит здесь свое время». Книги, которые потрясли: Чудеса природы, о которых должен знать каждый ребенок (Эдвин Брюстер) Природа физического мира (Артур Эддингтон) Алан Тьюринг Алан Тьюринг в возрасте 16 лет

Поворотным пунктом в жизни Тьюринга стало знакомство с Кристофером Моркомом (Christopher Morcom), с которым его объединил, в числе прочего, интерес к математике, астрономии. Кристофер Морком Они мечтали вместе изменить мир. Вместе готовились и сдавали экзамены в Кембридж. Кристофер был принят, а Алан нет. В феврале 1930 года Крису неожиданно стало плохо. Его увезли в больницу, сделали две операции, но это не помогло через неделю его не стало. Причина туберкулез, которым он заразился в детстве. Алан Тьюринг решил, что теперь он должен жить не только за себя, но и за него и должен был совершить в науке то, что не смог Крис. Работы Криса всегда были лучше моих, писал Тьюринг, «он был невероятно одарен».

Королевский колледж, Кембридж Книги, которые потрясли: Математические основы квантовой механики, (Джон фон Нейман) Вернер Гейзенберг, Эрвин Шредингер (труды по квантовой механике) Введение в математическую философию (Бертран Рассел) Основы арифметики (Готлиб Фреге) Магистерская диссертация: Центральная предельная теорема теории вероятности Научный руководитель (и коллега во всей дальнейшей жизни): математик (тополог) Макс Ньюмен (). Maxwell Herman Alexander "Max" Newman

Тезис Чёрча – Тьюринга: доказательство принципиальной неразрешимости «проблемы разрешимости» (доказательства непротиворечивости системы аксиом обычной арифметики) Давида Гильберта. Опровержение надежд Д. Гильберта и его последователей, полагавших, что математику как самую формализованную часть человеческого знания можно представить в виде набора аксиом и теорем. Именно для решения этой задачи Тьюрингом было разработано понятие абстрактной цифровой вычислительной машины. Четкое определение понятия метода как некоего алгоритма, который может быть выполнен механически, без творческого вмешательства. Модель вычислительного процесса: каждый алгоритм разбивается на последовательность простых, элементарных шагов Неэффективность построения специализированных вычислительных машин и идея универсальной электронной вычислительной машины. Эта логическая конструкция и была впоследствии названа «машиной Тьюринга». (история создания)

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

(физическое воплощение идеи вычислительной машины) Принстонский университет, получение степени PhD. Работа с Алонзо Чёрчем, Джоном фон Нейманом, Альбертом Эйншейном и другими выдающимися физиками и математиками. Первые дискуссии по вычислительным и думающим машинам с Джоном фон Нейманом. Снова Кембридж: работа в Национальной физической лаборатории Кембриджа в группе по проектированию и созданию вычислительной машины АСЕ (Automatic Computing Engine). Манчестер: Работа в математическом отделе Макса Ньюмена над созданием вычислительной машины в должности ответственного за программирование. 21 июля 1948 года: запуск первой программы на созданной вычислительной машине Марк-1: первый действующий компьютер с хранимой программой. Написание первого руководства по программированию и первой шахматной программы.

(расшифровка кодов «Энигмы») Шифровальная машина Энигма Работа в Национальном центре кодирования и криптографии (National Codes Centre) в Блечли-Парке в рамках засекреченного проекта Ультра, целью которого был поиск метода расшифровки секретных немецких кодов, созданных с помощью электрической шифровальной машины Энигма. Создание специальных вычислительных машин для дешифровки немецких сообщений («Хит Робинсон», «Питер Робинсон», «Бомба» и других). Участие в создании Колосса - первой (не только в Англии, но и в мире) полностью электронной вычислительной машины (под руководством М. Ньюмена). «Я не хочу сказать, что мы выиграли войну благодаря Тьюрингу, но беру на себя смелость сказать, что без него мы могли бы ее и проиграть. И. Гуд

(постановка вопроса об искусственном интеллекте) Середина XX века: зарождение интереса к искусственному интеллекту как новому научному направлению. Статьи Intelligent Machinery («Мыслящие машины») (1948) и Computing Machinery and Intelligence, впоследствии переизданная под названием "Can the Machine Think?" (Может ли машина мыслить?) (1950). Постановка вопроса: не «может ли машина думать?», а «Может ли машина делать то, что можем делать мы (как мыслящие создания), то есть то, что мы называем «думанием». «Игра в имитацию» как критерий оценки мыслительной деятельности машины. Следствия: Впервые предложен некоторый операциональный критерий для ответа на вопрос «Может ли машина мыслить?». Лингвистический подход: вопрос о мышлении машины сведен к вопросу о том, может ли машина адекватным образом общаться с человеком на естественном языке. (по Тьюрингу, «метод вопросов и ответов пригоден для того, чтобы охватить почти любую область человеческой деятельности, какую мы захотим ввести в рассмотрение»).

Преследования за гомосексуальность, обвинение в «непристойном поведении». 31 марта 1953 года - суд и приговор: тюремное заключение, либо инъекции женского гормона эстрогена (способ химической кастрации). Он выбрал второе. Увольнение из Департамента кодов. 8 июня 1954 года: тело Алана Тьюринга обнаружила домработница. Вердикт следствия: самоубийство путем отравления цианистым калием. 10 сентября 2009 года: Премьер- министр Великобритании Гордон Браун публично принёс извинения за преследования, которым был подвергнут Алан Тьюринг и тысячи других мужчин- геев, осуждённых по гомофобным законам. Яблоко… библейский символ познания и греха, символ трагической любви и смерти самого Тьюринга; намек на яблоко, вдохновившее Исаака Ньютона на создание теории гравитации; знаменитый логотип компании Apple с надкусанным яблоком…

Новая волна популярности Алана Тьюринга начинается в самом конце 20 века, когда он становится известен не только и не столько благодаря своему вкладу в компьютерные науки и математику, сколько как человек, пострадавший из-за своей нестандартности, своего рода культурный герой, символ и надежда всех гонимых и преследуемых. Огромное количество биографический и исследовательской литературы. Упоминания в исторических и фантастических романах Нила Стивенсона, Роберта Харриса, Гарри Гаррисона, Марвина Мински, Уильяма Гибсона. Как минимум две оперы и несколько песен, в том числе, на китайском языке. Постановка в лондонском театре Вест-энда и на Бродвее пьесы «Breaking the Code» («Взламывая код»), получившей целый ряд наград: фильм «Breaking the Code» («Взламывая код»); 2011: фильм "Игра имитатора" (не завершен). 2002: 21 место в списке 100 величайших британцев в истории по результатам опроса ВВС. 1999: журнал Time назвал Тьюринга в числе 100 наиболее значимых людей 20 века.

В 1974 году Ассоциацией по вычислительной технике ACM (Association for Computing Machnery) учреждена премия имени Алана Тьюринга, признанная в мировом компьютерном сообществе высшей наградой. Также именем Алана Тьюринга названы: Памятники и монументы: в Блетчли Парке, на территории Орегонского университета, на территории университета Суррея, в Сэквилль парке в Манчестере. Компьютерные лаборатории целого ряда университетов. Аллея Алана Тьюринга (Alan Turing Road) на территории университета Суррея (Великобритания); Кольцевая дорога вокруг Манчестера - «Путь Тьюринга» (The Turing Way»), а мост, по которому она проходит, назван «Мостом Алана Тьюринга». (The Alan Turing Bridge). Учебные корпуса в университетах Манчестера, Оксфорд Брукс, University of Manchester, the Open University, Oxford Brookes University and Aarhus University (Дани), Международной школы информационных наук (Франция) и др. Ежегодные конференции и конкурсы в целом ряде городов мира. Язык программирования, созданный в 1982 году учеными университета в Торонто. Памятник Алану Тьюрингу на территории университета Суррея (Великобритания)

Сегодня, более, чем через 50 лет после публикации Тьюрингом первых результатов своей работы в области искусственного интеллекта, поставленные им вопросы не утрачивают актуальности и, более того, порождают новые интерпретации. Среди них: Минимальный интеллектуальный Signal-тест (MIST). Предложен Крисом Мак-Кинстри. Разрешены лишь два типа ответов «да» и «нет». Используется для сбора статистической информации для измерения производительности программ, реализующих искусственный интеллект. Тест бессмертия. Определяет, качественно ли передан характер человека, а именно возможно ли отличить скопированный характер от характера человека, послужившего его источником. Мета-тест Тьюринга. Субъект (в частности, компьютер) считают разумным, если он создал нечто, что он сам хочет проверить на разумность. Обратный тест Тьюринга. Модификация теста Тьюринга, в которой цель или одну или более ролей машины и человека поменяли местами. Задача компьютера - определить с кем он беседовал: с человеком или же с другим компьютером. CAPTCHA (от англ. Completely Automated Public Turing test to tell Computers and Humans Apart). Разновидность обратного теста. Цель предотвратить атаки автоматических систем на сайт.

Чрезмерный антропоморфизм: проверяется только способность машины походить на человека, а не разумность машины вообще. Тест не учитывает следующие возможности: Иногда поведение человека не поддается разумному толкованию. Некоторое разумное поведение не присуще человеку. Тест Тьюринга подвергается критике по нескольким критериям: Непрактичность: антропоморфизм теста приводит к тому, что он не может быть по-настоящему полезным при разработке разумных машин. Например, в авиационном проектировании мы вовсе не стремимся к созданию разумной машины, допускающей свойственные человеку ошибки. Возможность имитации интеллекта: тест Тьюринга явно бихевиористичен или функционалистичен: он лишь проверяет, как действует субъект. Машина, проходящая тест, может имитировать поведение человека в разговоре, просто «неинтеллектуально» следуя механическим правилам (известный пример: мысленный эксперимент американского философа Джона Роджерса Сёрля «Китайская комната»).

В статье «Is the Brains Mind a Computer Program?» («Является ли мозговое мышление компьютерной программой?»), опубликованной в 1990 году, Сёрль описывает доказывает, что при проведении теста Тьюринга не существует никакой возможности отличить действительно мыслительную деятельность программы от механического исполнения правильно подготовленным инструкциям. («Китайская комната» Дж. Р. Сёрля)

Тьюринг прогнозировал, что машины, в конце концов, будут способны пройти разработанный им тест. Он даже называл конкретные даты: к 2000 году, машины с объемом памяти около 125 МБ) будут способны обманывать 30% судей. На сегодняшний день еще ни одна программа пройти тест не смогла. Премия Лёбнера (англ. Loebner prize) премия размером в 100 тысяч долларов, учрежденная в 1990 году американским ученым и филантропом Хью Лебнером и присуждаемая победителю ежегодного конкурса, в котором компьютерные программы соревнуются в прохождении теста Тьюринга. Элиза (ELIZA) (названа в честь Элизы Дулитл из пьесы «Пигмалион» Бернарда Шоу) - одна из первых программ, принявших участие в конкурсе Лёбнера; создана немецко-американским ученым Джозефом Вейценбаумом в 1966 году. A.L.I.C.E. (аббревиатура от англ. Artificial Linguistic Internet Computer Entity, что дословно можно перевести как «Искусственное лингвистическое интернет-компьютерное существо») – лидер в своем роде программ, которая три раза (в 2000, 2001, 2004 годах) становилась победителем премии Лёбнера. Программа-собеседник A.L.I.C.E.

Итак, очевидно, следует признать, что на сегодняшний день прогнозы Алана Тьюринга в отношении искусственного интеллекта не сбылись, а потому вопрос «может ли машина мыслить?» по-прежнему остается открытым. Как и вопросы: должна ли машина мыслить? должна ли машина мыслить именно так, как это делает человек? так ли уж важен вопрос о достижении виртуальным разумом неотличимости от человеческого? И многие другие…

100 лет со дня рождения Алана Тьюринга Юлия Киселева Магистрант специальности «религиоведение», Донецкий национальный технический университет Материалы презентации доступны на сайте Ассоциации философов и религиоведов:

Слайд 2

Введение

Понятие алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату (Марков А.А.) Свойства алгоритма: 1) Дискретность. 2) Определенность. 3) Результативность. 4) Массовость.

Слайд 3

Математическая модель машины Тьюринга

Машина Тьюринга (МТ) – это математическая модель идеализированной цифровой вычислительной машины. Устройство машины Тьюринга. Лента. Считывающая головка. Устройство управления. Внутренняя память.

Слайд 4

Лента

В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A = {˄, a1,a2,…,an-1}, 2≥n . Пустая ячейка обозначается символом ˄, а сам символ ˄ называется пустым, при этом остальные символы называются непустыми.

Слайд 5

Считывающая головка

Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оставаться на месте (Н).

Слайд 6

Внутренняя память

Внутренняя память машины представляет собой некоторое конечное множество внутренних состояний Q = {q0, q1, … , qm}, m≥ 1. Будем считать, что мощность | Q |≥2. Два состояния машины имеют особое значение: q1 – начальное внутреннее состояние (начальных внутренних состояний может быть несколько), q0 – заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоянием.

Слайд 7

Устройство управления

Выполняет следующие действия: Изменяет считываемый в момент t символ ai на новый символ aj (в частности оставляет его без изменений, т. е. ai= aj); Передвигает головку в одном из следующих направлений: Н, Л, П; Изменяет имеющееся в момент t внутреннее состояние машины qi на новое qj , в котором будет машина в момент времени t +1. Такие действия устройства управления называют командой, которую можно записать в виде: qiaiajDqj

Слайд 8

Работа машины Тьюринга

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

Слайд 9

Если в начальный момент на ленте записано слово a1, a2,˄, a1 , a1 то начальная конфигурация будет иметь вид: Работа машины Тьюринга состоит в последовательном применении команд, причем, применение той или команды определяется текущей конфигурацией. Так в приведенном выше примере должна применятся команда с левой частью q1a1 . Результатом работы машины считается слово, которое будет записано на ленте в заключительной конфигурации, т. е. в конфигурации, в которой внутреннее состояние машины есть q0 .

Слайд 10

Примеры машины Тьюринга

Пример 1. Построить машину Тьюринга T1 , которая применима ко всем словам с внешним алфавитом {a,b} и делает следующее: любое слово x1,x2…xn , где xi = a или xi = b (i = 1, 2 … n) преобразует в слово x2, …xn, x1 т. е., начиная работать при слове x1,x2…xn на ленте в начальной конфигурации, машина остановится, и в заключительной конфигурации на некотором участке ленты будет записано слово x2, …xn, x1, а все остальные клетки ленты (если такие будут) окажутся пустыми.

Слайд 11

Решение: За внешний алфавит машины T1 возьмем множество A={˄, a, b} , а за внутренний – Q = {q0, q1, q2, q3}. Команды определим следующим образом: q1a ˄Пq2, q1b ˄Пq3, qiy ˄ППi, где yϵ{a, b}, i =2, 3; q2˄ aHq0, q3˄ bHq0 Рассмотрим работу машины T1 над словом ba . В работе машины над словом ba начальная конфигурация имеет следующий вид:

Более короткая запись этой последовательности конфигураций, т. е. процесса работы машины будет: Таким образом, слово bbabb переработано машиной в слово babbb .

Посмотреть все слайды

Определение машины Тьюринга

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

Структура и описание машины Тьюринга Машина Тьюринга состоит из: бесконечной ленты, разделенной на ячейки; каретки (читающей и записывающей головки); программируемого автомата (программа в виде таблицы). Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую букву он видит, а также в зависимости от своего состояния q автомат может выполнять следующие действия: записать новую букву в обозреваемую ячейку; выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным; перейти в новое состояние.

1) Внешний алфавит А = { a 0 , a 1 , …, a n } Элемент a 0 называется пустой символ или пустая буква (признак того, что ячейка пуста). В этом алфавите в виде слова кодируется исходный набор данных и результат работы алгоритма. Устройство машины Тьюринга

2) Внутренний алфавит Q = { q 0 , q 1 , …, q m }, { П, Л, Н! } В любой момент времени машина Тьюринга находится в одном из состояний q 0 , q 1 , …, q m При этом: q 1 - начальное состояние (машина начинает работу) q 0 - заключительное состояние (машина закончила работу) Символы { П, Л, Н! } – символы сдвига (вправо, влево, на месте) Устройство машины Тьюринга

Виды команд машины Тьюринга Написать новую букву в обозреваемую ячейку Выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться на месте (П, Л, Н) Перейти в новое состояние. а 0 а 1 … а i … а j q 0 q 1 … a k { ЛПН } q m q i … q j 1 1 1 * 1 1 Указание о смене символа Указание о сдвиге каретки Указание о смене внутреннего состояния

3) Внешняя память (лента) Машина имеет ленту, разбитую на ячейки, в каждую из которых может быть записана только одна буква Устройство машины Тьюринга

3) Внешняя память (лента) Устройство машины Тьюринга Пустая клетка содержит a 0 . В каждый момент времени на ленте записано конечное число непустых букв Лента является конечной, но дополняется в любой момент ячейками слева и справа для записи новых непустых символов. Это соответствует принципу абстракции потенциальной осуществимости

4) Каретка (управляющая головка) Каретка машины располагается над некоторой ячейкой ленты – воспринимает символ, записанный в ячейке В одном такте работы каретка сдвигается на одну ячейку (вправо, влево) или остается на месте Устройство машины Тьюринга

5) Функциональная схема (программа) Программа машины состоит из команд: Устройство машины Тьюринга Для каждой пары (q i , a j) программа машины должна содержать одну команду (детерминированная машина Тьюринга)

К началу работы машины на ленту подается исходный набор данных в виде слова  Описание работы машины Тьюринга Будем говорить, что непустое слово  в алфавите А\ {a 0 } воспринимается машиной в стандартном положении, если: - оно задано в последовательных ячейках ленты, - все другие ячейки пусты, - машина обозревает крайнюю правую ячейку из тех, в которых записано слово 

Описание работы машины Тьюринга Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q 1 (стоп-состоянии q 0)

Находясь в не заключительном состоянии, машина совершает шаг, который определяется текущим состоянием q i и обозреваемым символом a j Описание работы машины Тьюринга

Описание работы машины Тьюринга В соответствии с командой q i a j  q k a l Х выполняются следующие действия: 1) Содержимое обозреваемой ячейки a j стирается и в нее записывается символ a l (который может совпадать с a j) 2) Машина переходит в новое состояние q k (оно может совпадать с состоянием q i) 3) Каретка перемещается в соответствии с управляемым символом Х  { П, Л, Н! }

При переходе машины в заключительное состояние q 0 ее работа прекращается На ленте записан результат работы алгоритма – слово  в алфавите А\ {a 0 } Описание работы машины Тьюринга

Машинным словом (конфигурацией) машины Тьюринга называется слово вида  1 q k a l  2 , где  1 и  2 - слова в алфавите А.

Конфигурация  1 q k a l  2 интерпретируется следующим образом: - машина находится в состоянии q k - каретка обозревает на ленте символ a l -  1 и  2 – это содержимое ленты до и после символа a l

Ситуации неприменимости машины Тьюринга Считается, что машина Тьюринга неприменима к данному входному слову, если в программе нет клеток останова или машина в процессе работы на них не попадает. Например: Машина Тьюринга применима к данному входному слову, если, начав работу над этим входным словом, она рано или поздно дойдёт до одной из клеток останова. Как изменилась программа в примере? а 0 0 1 q 1 1П q 1 0П q 1 1П q 1 а 0 0 1 q 1 1Н q 0 0П q 1 1П q 1

Пример машин Тьюринга Требуется построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б» и наоборот. а 0 а б в … я q 1 а 0 Н! б Л q 1 а Л q 1 в Л q 1 … я Л q 1 у  у б  а а  б р  р у б а р а б а  б б  а а б б а

Реализуйте предложенный алгоритм Машина Тьюринга прибавляет единицу к числу на ленте. Входное слово состоит из цифр целого десятичного числа, записанного в последовательные ячейки на ленте. В начальный момент машина находится против самой правой цифры числа. а 0 0 1 2 3 4 … 7 8 9 q 1 1Н q 0 1Н q 0 2Н q 0 3Н q 0 4Н q 0 5Н q 0 … 8Н q 0 9Н q 0 0Л q 1

Реализуйте предложенный алгоритм На ленте машины Тьюринга содержится последовательность символов «+». Машина Тьюринга каждый второй символ «+» заменяет на «–». Замена начинается с правого конца последовательности. Автомат в состоянии q 1 обозревает один из символов указанной последовательности. а 0 + – q 1 а 0 Л q 2 + П q 1 q 2 а 0 Н! + Л q 3 q 3 а 0 Н! – Л q 2 q 1 – машина ищет правый конец числа; q 2 – пропускает знак «+», при достижении конца последовательности – останов; q 3 – знак «+» заменяет на « – ».

Пример Дана машина Тьюринга с внешним алфавитом А = { a 0 , 1, * } , алфавитом внутренних состояний Q = { q 0 , q 1 , q 2 , q 3 }, и следующей функциональной схемой: Применить машину Тьюринга к слову  =11*1, начиная со стандартного начального положения

Решение 1) Заменяем содержимое обозреваемой ячейки 1 на а 0

Решение 2) Машина переходит в новое состояние q 2

Решение 3) Каретка перемещается влево

Решение Полное подробное решение

Решение Решение, записанное с помощью конфигураций (в строчку)

 = 1*11 Ответ:  = 111

Литература Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2008. - 448 с. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. – СПб.: Лань, 1999. - 288 с. Ильиных А.П. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. - 149 с.

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

«Современные партийные системы» - Определение современной партии. Партии. Идеологическая функция. Английские партии. Признаки партий. Небольшое количество членов. Партии власти. Особое положение в обществе. Подходы к определению понятия «партия». Сущность и принципиальное различие между идеологиями. Консервативная и либеральная партии.

«Социальная защита» - Труд стал основанием социального признания и фундаментом для защиты от различных опасностей и несчастий. Вопрос: Что из двух факторов стало причиной чрезвычайного низкого уровня увольнений? Кризис социального государства. 3. Противоречивый характер системы социальной защиты. При изменении конъюнктуры неожиданным наследством оказываются долги, способные расстроить положение трудящихся.

«ЕГЭ по обществознанию С8» - Правонарушение. Развернутый ответ по теме. Суть плана. Общественно-опасное виновное деяние. Назывная форма плана. Преодоление экологического кризиса. Что такое правонарушение. Проступки. Смысловые элементы. Развернутый план. Экологический кризис связан с другими глобальными проблемами. Деформации в сознании людей.

«Готика» - В наше время готика распространилась почти во всех стилях музыки. Среди готов есть атеисты, христиане и сатанисты. What is it? Монахи, садо-мазохисты, фетишисты. Спор о Свете и Тьме. Почему именно черный цвет? Выполнила Батина Юлия. Радость и грусть, как свет и тьма - два измерения. Далее был готический роман и поэзия - Байрон, Волпоул, Анна Райс.

«Российская Конституция» - Что такое Конституция. Президент РФ. Что такое национальные ценности. Назовите людей, делами которых гордится Россия. Выражение «соединённые общей судьбой на одной земле». 20 лет Конституции Российской Федерации. Что значит принять судьбу отечества как свою личную. Преамбула. Конституция и её роль. Преамбула Конституции РФ.

«Учения об обществе и человеке» - Постмарксизм. Учения об обществе и человеке. Функции. Г.В.Ф.Гегель. Аристотель. Формы государственного правления. Древняя Индия. Человек. Возрождение. Древний Китай. Представители. Техницизм. Экзистенциализм. Материалистическое понимание общества. Мифы. Ценностный подход. Адам Смит. Средние века. Сущность теории общественного договора.

Алан Тьюринг

А́лан Мэ́тисон Тью́ринг А́лан Мэ́тисон Тью́ринг (англ. Alan Mathison Turing ; 23 июня 1912 - 7 июня 1954) - английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Кавалер Ордена Британской империи (1945), член Лондонского королевского общества (1951). Предложенная им в 1936 году абстрактная вычислительная «Машина Тьюринга», которую можно считать моделью компьютера общего назначения, позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований. Научные труды А. Тьюринга - общепризнанный вклад в основания информатики (и, в частности, - теории искусственного интеллекта).

Время Войны Во время Второй мировой войны Алан Тьюринг работал в Правительственной школе кодов и шифров, располагавшейся в Блетчли -парке, где была сосредоточена работа по взлому шифров и кодов стран оси. Он возглавлял группу Hut 8, ответственную за криптоанализ сообщений военно-морского флота Германии. Тьюринг разработал ряд методов взлома, в том числе теоретическую базу для Bombe - машины, использованной для взлома немецкого шифратора Enigma .

Машина Тьюринга В течение нескольких недель после прибытия в Блэтчли -парк Тьюринг написал спецификации к электромеханической машине, которая могла помочь со взломом « Энигмы » более эффективно, чем польская « криптологическая бомба». Машина Тьюринга с улучшениями, предложенными математиком Гордоном Велшманом, стала важнейшим инструментом для расшифровки сообщений « Энигмы ». Машина получила название Bombe . Машина искала возможные настройки, использованные для шифрования сообщений (порядок роторов, положение ротора, соединения коммутационной панели), опираясь на известный открытый текст. Для каждой возможной настройки ротора (у которого было 1019 состояний или 1022 в модификации, использовавшейся на подводных лодках) машина производила ряд логических предположений, основываясь на открытом тексте (его содержании и структуре). Далее машина определяла противоречие, отбрасывала набор параметров и переходила к следующему. Таким образом, большая часть возможных наборов отсеивалась и для тщательного анализа оставалось всего несколько вариантов. Первая машина была запущена в эксплуатацию 18 марта 1940 года. Перебор ключей выполнялся за счёт вращения механических барабанов, сопровождавшегося звуком, похожим на тиканье часов.

Colossus В июле 1942 года Тьюринг принял участие в расшифровке кода «Лоренц», применявшегося немцами для передачи сообщений высшего командования. «Лоренц» был существенно сложнее « Энигмы » и не поддавался расшифровке существовавшими методами. Тьюринг предложил использовать в конструкции дешифратора электронные лампы и привел в команду Т. Флауэрса - опытного инженера-электронщика. В результате совместных усилий математиков и инженеров был разработан «Колосс» - одна из первых в мире ЭВМ. К 1944 с помощью «Колосса» код «Лоренц» был взломан, что позволило союзникам читать всю переписку высшего германского руководства. По некоторым оценкам, это приблизило поражение Германии на несколько лет

Ранние компьютеры и тест Тьюринга С 1945 по 1947 год Тьюринг проживал в Ричмонде и работал над ACE(Automatic Computing Engine) в Национальной физической лаборатории. 19 февраля 1946 он представил работу, которую можно назвать первым детальным описанием компьютера с хранимой в памяти программой. Незаконченная работа "Первый проект отчёта о EDVAC" (1945) Фон Неймана, предшествовала ей, но была намного менее детальна, а согласно руководителю математического отделения Национальной физической лаборатории - Джону Воурмслей:она содержит ряд идей, которые принадлежат доктору Тьюрингу. Несмотря на то, что постройка ACE была вполне осуществима, секретность, окружавшая Блэтчли -парк привела к задержкам в начале работ, что разочаровало Тьюринга. К концу 1947 года он вернулся в Кембридж ради годичного отпуска в течение которого он плодотворно работал над « Intelligent Machinery », которая не была опубликована прижизненно. Пока Алан Тьюринг пребывал в Кембридже Pilot ACE был построен в его отсутствие. Он выполнил свою первую программу 10 мая 1950 года. Хотя полная версия ACE никогда не была построена, некоторые компьютеры имели с ним много общего, к примеру DEUCE и Bendix G-15

В 1948 году Алан Тьюринг получил звание Reader (англ.) в математическом департаменте Манчестерского университета (англ.). Там в 1949 году он стал директором Компьютерной Лаборатории, где была сосредоточена работа по программированию Манчестерского Марка I. В то же время Тюринг продолжал работать над более абстрактными математическими задачами, а в своей работе " Computing Machinery and Intelligence " (англ.)(журнал « Mind », октябрь 1950) он обратился к проблеме искусственного интеллекта и предложил эксперимент, ставший впоследствии известным, как тест Тьюринга. Его идея заключалась в том, что можно считать, что компьютер «мыслит», если человек, взаимодействующий с ним, не сможет в процессе общения отличить компьютер от другого человека. В этой работе Тьюринг предположил, что вместо того чтобы пытаться создать программу, симулирующую разум взрослого человека, намного проще было бы начать с разума ребёнка, а затем обучать его. CAPTCHA, основанный на обратном тесте Тьюринга, широко распространён в интернете. В 1948 году Алан совместно со своим бывшим коллегой Дэвидом Чамперновном (англ.) начал писать шахматную программу для компьютера, который ещё не существовал. В 1952 году, не имея подходящего устройства для её выполнения, Тьюринг сыграл игру, в которой симулировал действия машины, делая по одному ходу раз в полчаса. Игра была записана и в результате программа проиграла коллеге Тьюринга Алеку Глини, но выиграла партию у жены Чамперновна. Тьюринг также изобрёл метод LU-разложение в 1948, который сегодня используется для решения уравнений.