From 18696d3227b624a65613cbf797b53aefce1201ec Mon Sep 17 00:00:00 2001 From: Andrew Date: Sun, 18 Oct 2020 18:09:45 +0400 Subject: =?UTF-8?q?=D0=9F=D0=B5=D1=80=D0=B5=D0=BC=D0=B5=D1=81=D1=82=D0=B8?= =?UTF-8?q?=D0=BB=20=D0=B4=D0=BE=D0=BA=D0=BB=D0=B0=D0=B4=20=D0=BE=20=D0=A2?= =?UTF-8?q?=D1=8C=D1=8E=D1=80=D0=B8=D0=BD=D0=B3=D0=B5=20=D0=B2=20=D1=8D?= =?UTF-8?q?=D1=82=D0=BE=D1=82=20=D1=80=D0=B5=D0=BF=D0=BE=D0=B7=D0=B8=D1=82?= =?UTF-8?q?=D0=BE=D1=80=D0=B8=D0=B9?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- turing/AlanTuring.tex | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 116 insertions(+) create mode 100644 turing/AlanTuring.tex (limited to 'turing/AlanTuring.tex') diff --git a/turing/AlanTuring.tex b/turing/AlanTuring.tex new file mode 100644 index 0000000..0d6d856 --- /dev/null +++ b/turing/AlanTuring.tex @@ -0,0 +1,116 @@ +\documentclass{article} +\usepackage[utf8]{inputenc} +\usepackage[russian]{babel} +\usepackage{hyperref} +\usepackage{underscore} +\usepackage{setspace} +\usepackage{indentfirst} +\singlespacing + +\author{Андрей Гущин, 131 группа} +\title{Вклад Алана Тьюринга в развитие информатики.} + +\begin{document} + +\maketitle + +\section{Кто такой Алан Тьюринг?} +\textbf{Алан Мэтисон Тьюринг} (англ. Alan Mathison Turing; 23 июня 1912 — 7 июня 1954) +— английский математик, логик, криптограф, оказавший существенное влияние на развитие +информатики. Кавалер Ордена Британской империи (1945), член Лондонского королевского +общества (1951). Предложенная им в 1936 году абстрактная вычислительная +«Машина Тьюринга», которую можно считать моделью компьютера общего назначения, +позволила формализовать понятие алгоритма и до сих пор используется во множестве +теоретических и практических исследований. Научные труды А. Тьюринга — общепризнанный +вклад в основания информатики (и, в частности, — теории искусственного интеллекта).[\ref{itm:bio}] + +\section{Вклад в информатику} +\subsection{Проблема останова} +\textbf{Проблема остановки} (или проблема останова) — это одна из центральных проблем в +теории алгоритмов, которая может неформально быть поставлена в виде: +Даны описание процедуры и её начальные входные данные, требуется определить, +завершится ли когда-либо выполнение процедуры с этими данными. +Альтернативой этому является то, что она работает всё время без остановки.[\ref{itm:problem-def}] + +Алан Тьюринг доказал в 1936 году, что проблема остановки неразрешима на машине Тьюринга. +Другими словами, не существует общего алгоритма решения этой проблемы.[\ref{itm:problem-sol}] + +Проблема остановки занимает центральное место в теории вычислимости, поскольку +представляет собой первый пример задачи, которую невозможно решить алгоритмическим +путём. Для многих других задач можно доказать их алгоритмическую неразрешимость, +попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: +пусть есть некая задача, для которой требуется установить её неразрешимость. +Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать +алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, +ведь известно, что не существует такого алгоритма. А значит, предположение было +неверным и исходная задача также неразрешима. + +\subsection{Машина Тьюринга} +\textbf{Машина Тьюринга} - название, закрепившееся за абстрактными (воображаемыми) +«вычислительными машинами» некоторого точно охарактеризованного типа, дающими +пригодное для целей математического рассмотрения уточнение общего интуитивного +представления об Алгоритме. Концепция такого рода машины сложилась в середине +30-х гг. 20 в. у А. М. Тьюринга в результате произведённого им анализа действий +человека, выполняющего в соответствии с заранее разработанным планом те или иные +вычисления, то есть последовательные преобразования знаковых комплексов.[\ref{itm:machine-def}] + +Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на +ячейки, и автомата (головки), которая управляется программой. + +Программы для машин Тьюринга записываются в виде таблицы, где первые столбец +и строка содержат буквы внешнего алфавита и возможные внутренние состояния +автомата (внутренний алфавит). Содержимое таблицы представляет собой команды +для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она +находится в данный момент), и внутренне состояние головки определяют, какую +команду нужно выполнить. Команда определяется пересечением символов внешнего +и внутреннего алфавитов в таблице. + +Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие: +\begin{itemize} + \item \textbf{Внешний алфавит}. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. + \item \textbf{Внутренний алфавит}. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова. + \item \textbf{Таблица переходов}. Описание поведения автомата (головки) в зависимости от состояния и считанного символа. +\end{itemize} + +Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия: +\begin{itemize} + \item Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой). + \item Передвигаться на одну ячейку влево или вправо. + \item Менять свое внутреннее состояние. +\end{itemize} + +Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию +этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит +автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать +и не все составляющие (например, не менять символ, не передвигаться или не менять +внутреннего состояния).[\ref{itm:machine-work}] + +\subsection{Тезис Чёрча-Тьюринга} +\textbf{Тезис Чёрча} - принцип, согласно к-рому класс функций, вычислимых с помощью алгоритмов +в широком интуитивном смысле, совпадает с классом частично рекурсивных функций. Ч. т.- +это естественнонаучный факт, подтверждаемый опытом, накопленным в математике за всю ее +историю. Все известные в математике примеры алгоритмов удовлетворяют ему. Ч. т. впервые +был высказан А. Чёрчем \textit{(A. Church, 1936)}.[\ref{itm:church-def}] + +Различным уточнениям интуитивного понятия алгоритма соответствуют свои формулировки +Ч. т. Тезис Тьюринга заключается в том, что всякая вычислимая в интуитивном смысле +функция вычислима с помощью нек-рой Тьюринга машины, апринцип нормализации Маркова - +в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью нек-рого +нормального алгорифма. Из эквивалентности известных уточнений понятия алгоритма следует +эквивалентность соответствующих вариантов Ч. т. Этот факт является еще одним +подтверждением Ч. т. Тезис Чёрча не может быть строго доказан, так как в его +формулировке участвует неточное понятие алгоритм в интуитивном смысле.[\ref{itm:problem-sol}] + +\pagebreak +\section*{Источники} +\begin{enumerate} + \item \label{itm:bio} Сайт Википедия. \textit{Алан Тьюринг} // \href{https://ru.wikipedia.org/wiki/%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3,_%D0%90%D0%BB%D0%B0%D0%BD}{Ссылка} + \item \label{itm:problem-def} Сайт Википедия. \textit{Проблема останова} // \href{https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8}{Ссылка} + \item \label{itm:problem-sol} Алан Тьюринг. \textit{On Computable Numbers, with an Application to the Entscheidungsproblem} // \href{https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf}{Ссылка} + \item \label{itm:machine-def} Большая советская энциклопедия. \textit{Машина Тьюринга} // \href{https://dic.academic.ru/dic.nsf/bse/141979/Тьюринга}{Ссылка} + \item \label{itm:machine-work} Статья на сайте \url{https://inf1.info}. \textit{Машина Тьюринга} // \href{https://inf1.info/turing}{Ссылка} + \item \label{itm:church-def} Математическая энциклопедия. \textit{Тезис Чёрча} // \href{https://dic.academic.ru/dic.nsf/enc_mathematics/6170/%D0%A7%D0%81%D0%A0%D0%A7%D0%90}{Ссылка} +\end{enumerate} + + +\end{document} -- cgit v1.2.3