1 files changed, 116 insertions, 0 deletions
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}