Пятница, 25.09.2020, 14:38
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 6
Гостей: 6
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ

Машина Тьюринга и «Колосс»
19.01.2016, 12:44

Алан Тьюринг (1912–1954) в детстве хотел стать врачом, но в итоге стал математиком, философом и специалистом по криптографии, а также создателем современной информатики. Он известен в первую очередь благодаря своим теоретическим работам, однако также сыграл очень важную роль в практической реализации одного из первых компьютеров. Тьюринг сделал свое первое открытие в теоретической математике в 1936 году, решив проблему разрешения (Entscheidungsproblem), сформулированную Давидом Гильбертом. Чтобы справиться с этой задачей, Тьюринг создал модель вычислений, в которой дал формальное определение алгоритму (или программе). Эта модель вошла в историю под названием машина Тьюринга.

В 1928 году влиятельный немецкий математик Давид Гильберт (1862–1943), который в 1900 году предложил знаменитый список задач, начал работу над проблемой разрешения, которую впервые сформулировал Лейбниц. Гильберт считал, что нерешаемых задач не существует. Он предложил гипотезу, согласно которой всегда можно составить программу (алгоритм), которая сможет дать однозначный верный ответ на любой заданный вопрос. Независимо друг от друга Алан Тьюринг и американский математик Алонзо Чёрч доказали, что Гильберт ошибался: нерешаемые задачи существуют, а предложенную Гильбертом программу (алгоритм) составить невозможно. Следовательно, математика не является разрешимой, то есть не существует метода, который позволил бы определить истинность или ложность произвольного математического утверждения.



Математик Алан Тьюринг, считающийся одним из создателей компьютеров.


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

Он свел проблему разрешения к проблеме остановки и доказал, что она неразрешима с помощью его машины: нельзя определить алгоритмически, завершит ли данная машина Тьюринга свою работу в какой-то момент или нет. Чёрч и Тьюринг не соперничали; напротив, оба осознавали, что их модели, несмотря на формальные различия, были одинаково мощными, и объединили усилия.

* * *

КАК РАБОТАЕТ МАШИНА ТЬЮРИНГА?

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

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

В своем доказательстве он использовал лямбда-исчисление, разработанное им совместно с коллегой Стивеном Клини, которое радикально отличалось от машины Тьюринга. Тьюринг опубликовал свое решение проблемы разрешения в августе того же 1936 года. Это была его знаменитая статья «О вычислимых числах в приложении к проблеме разрешения», в которой были переформулированы результаты Курта Гёделя (1906–1978) о пределах доказуемости и вычислений, а также содержались ссылки на работу Чёрча. Вместо того чтобы спорить, кто совершил открытие первым, в сентябре того же года Тьюринг переходит на работу в Принстонский университет, чтобы написать диссертацию о проблеме разрешения под руководством Чёрча. Он защитил диссертацию в 1938 году, получил степень доктора и вернулся в Кембридж. Этот удачный союз талантов принес немалую выгоду всему человечеству.

* * *

БЛЕТЧЛИ-ПАРК И ЭНИГМА

Легендарное шифровальное подразделение Великобритании Блетчли-парк располагалось в графстве Бакингемшир в 80 километрах от Лондона. Во время Второй мировой войны наиболее авторитетные английские ученые работали в Блетчли-парке над взломом немецких шифров. Это подразделение располагалось в одноименном викторианском поместье (сегодня музей криптографии). В Блетчли-Парке был расшифрован код шифровальной машины «Энигма». Эта машина содержала шифровальный механизм, состоящий из вращающихся роторов и колец, который позволял вооруженным силам нацистской Германии расшифровывать и зашифровывать сообщения. Усилия британских ученых по взлому шифра «Энигмы» не пропали даром: считается, что прочтение предположительно секретных сообщений немцев позволило приблизить окончание войны на несколько лет.



* * *

Эти значимые события, касающиеся наиболее теоретической области науки, происходили в один из самых драматичных моментов современной истории. Политическая ситуация в Европе накалялась, и мир двигался к войне. Опасаясь, что Англия вступит в войну с Германией, Тьюринг во время работы над диссертацией начал заниматься криптографией. Британское правительство в 1939 году пригласило его работать в Блетчли-парке вместе с другими исследователями. Перед ними стояла задача взломать секретный шифр немецкой армии — код «Энигмы». Благодаря своим знаниям Тьюринг смог взломать шифр немецких воздушных сил в середине 1941 года, однако в феврале 1942 шифр был усложнен, и сообщения немцев снова стало невозможно прочесть.

Чтобы расшифровать их, Тьюринг и его коллеги разработали несколько вычислительных машин. Тьюринг еще во время работы в Принстоне изобрел машину, позволявшую выполнять умножение. Группа Тьюринга создала машину под названием «Колосс», которая считается первым электронным программируемым компьютером в мире. Было построено десять экземпляров «Колосса». Первый из них начал работу в декабре 1943 года, на два года раньше, чем американский ENIAC. В конце 1942 — начале 1943 года Тьюринг совершил новую поездку в США, чтобы помочь американским военным взломать немецкие шифры. Во время поездки он познакомился с Клодом Шенноном, создателем теории информации и автором определения энтропии.

После окончания войны Тьюринга пригласили в Национальную физическую лабораторию (National Physical Laboratory), отвечавшую за развитие научно-технических стандартов в Великобритании. Там он разработал ACM (Automatic Computer Machine) — автоматическую компьютерную машину — и сформулировал понятие микропрограммирования как способа задания и изменения команд арифметико-логического устройства. Существует и альтернативный вариант, при котором арифметико-логическое устройство реализовано в оборудовании компьютера и его операции изменять нельзя. Тьюринг также определил понятия подпрограммы и программной библиотеки.

Весь 1947 год он отдыхал в Кембридже, где написал статью, в которой представил нейронную сеть — модель, использующую понятия из физиологии и неврологии. В следующем году, увидев, что работы над автоматической компьютерной машиной остановились, он перешел на службу в Манчестерский университет, где начал работу над программным обеспечением компьютера Mark I Максвелла Ньюмана.

В этот период он создал свои наиболее абстрактные работы. Он написал знаменитую статью «Вычислительные машины и разум», опубликованную в журнале Mind в октябре 1950 года, в которой изложил свою точку зрения на искусственный интеллект и описал знаменитый эксперимент, известный как тест Тьюринга. Целью эксперимента было определить, может ли машина мыслить.



Два оператора работают на «Колоссе» Mark 2.

* * *

ПОСТЫДНАЯ НЕСПРАВЕДЛИВОСТЬ

Математик и логик, который в немалой степени определил облик современного мира, в последние годы жизни подвергся столь постыдному и несправедливому преследованию со стороны полного предрассудков послевоенного британского общества, что это стоило ему жизни. Блестящая карьера Алана Тьюринга прервалась, когда его начали преследовать за нетрадиционную сексуальную ориентацию, которая в то время считалась в Великобритании преступлением. От подобных обвинений за 50 лет до этого пострадал Оскар Уайльд. Тьюринг знал, что ему нечего стыдиться, и начался судебный процесс, широко освещавшийся в прессе. Суд предложил ему выбор между тюремным заключением и гормональной терапией для подавления либидо. Желая избежать тюрьмы, он согласился на лечение, которое продолжалось в течение года, привело к значительным изменениям в организме ученого и сделало его импотентом. После этого Тьюринг покончил жизнь самоубийством, приняв цианид. Еще более примечательно, что в письмах коллегам он выражал беспокойство по поводу того, что эти обвинения бросят тень на его работы по искусственному интеллекту, которые он сам считал крайне важными для всего человечества. В 2009 году Гордон Браун, который в то время занимал пост премьер-министра Великобритании, публично принес извинения от имени британского правительства за преследование, которому подвергся Алан Тьюринг в последние годы жизни. С момента смерти Тьюринга, который оказал неоценимые услуги своей стране и всему цивилизованному миру в борьбе с нацизмом, прошло почти 60 лет.

* * *

В 1951 году он был избран членом Лондонского королевского общества. Однако в конце жизни он не получил того признания, которого заслуживал. В 1966 году, спустя несколько лет после его трагической гибели, Ассоциация вычислительной техники учредила премию, носящую его имя, — премию Тьюринга, которая считается эквивалентом Нобелевской премии в информатике. Среди лауреатов премии — ученые, совершившие выдающиеся открытия в области аппаратного и программного обеспечения, баз данных, теоретических основ информатики (включая криптографию) и компьютерных сетей.

Категория: АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ | Добавил: admin | Теги: ИТК и мате, Мир Математики, искусственный интеллект, машинное обучение, популярная математик, математика и информатик, дидактический материал по матем
Просмотров: 701 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ


ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2020
    Яндекс.Метрика Рейтинг@Mail.ru