1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
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}
|
