<commit_before>%% -*- coding:utf-8 -*-
\section{Машина Тюринга}
\label{addTuring}

Машина Тюринга $TM$ - математический объект состоящий из
головки (head) и бесконечной ленты разделенной на ячейки в каждой из
которых может быть записан один символ.

\input ./add/algo/figturing.tex

Головка $TM$ может находится в одном из состояний $q_i \in Q$, где $Q$
- множество различных состояний. Состояние в котором $TM$ находилась в
начальный момент времени $q_0 \in Q$ называется начальным состоянием. 

Среди элементов множества $Q$ выбрано подмножество $F \subset Q$
финальных состояний. Если $TM$ оказалась в состоянии $f \in F \subset
Q$, то говорят что машина Тюринга завершила (terminate) свою работу.

Символы записанные на ленту образуют некоторое множество (алфавит)
$\Gamma = \left\{\gamma_i\right\}$.

Входным алфавитом $\Sigma$ машины Тюринга называется называется
подмножество элементов $\Gamma$ которыми оперирует головка $MT$,
т. е. те символы, которые она может распознать на ленте. Те символы,
которые головка не может распознать мы будем обозначать символом
$\beta$ (blank).

В процессе работы $TM$ она выполняет следующие действия:
\begin{itemize}
\item{считывает элемент на который указывает головка
  (см. рис. \ref{figAddAlgoTuring})}
\item{изменяет (или оставляет неизменным) этот символ на элемент
  $\sigma \in \Sigma \subset \Gamma$}
\item{изменяет положение головки на одну ячейку вправо ($R$) или влево
($L$)}
\end{itemize}

Изменение состояния $MT$ описывается таблицей переходов
$\Delta$. Элемент таблицы переходов записывается в следующем виде: 
$\delta_j\left(q_{old}, \gamma_{old}\right)$ где $q_{old} \in Q$ текущее состояние,
$\gamma_{old} \in \Gamma$ - выбранный элемент на ленте. Значение
перехода может быть 
неопределено или записано в виде $\left\{q_{new}, \gamma_{new}, d\right\}$, где
$q_{new} \in Q$ - новое состояние машины Тюринга, $\gamma_{new} \in \Gamma$ -
новое значение элемента на ленте на который указывала головка,
т. е. $\gamma_{old}$ заменяется на $\gamma_{new}$. $d \in D =
\left\{L, R\right\}$ - направление
движения головки ($L$ налево, $R$ направо). В случае неопределенного
перехода говорят, что машина Тюринга зависла (halt) в состоянии $q_{old}$.


<commit_msg>turing machine<commit_after>%% -*- coding:utf-8 -*-
\section{Машина Тюринга}
\label{addTuring}

Машина Тюринга $TM$ - математический объект состоящий из
головки (head) и бесконечной ленты разделенной на ячейки в каждой из
которых может быть записан один символ.

\input ./add/algo/figturing.tex

Головка $TM$ может находится в одном из состояний $q_i \in Q$, где $Q$
- множество различных состояний. Состояние в котором $TM$ находилась в
начальный момент времени $q_0 \in Q$ называется начальным состоянием. 

Среди элементов множества $Q$ выбрано подмножество $F \subset Q$
финальных состояний. Если $TM$ оказалась в состоянии $f \in F \subset
Q$, то говорят что машина Тюринга завершила (terminate) свою работу.

Символы записанные на ленту образуют некоторое множество (алфавит)
$\Gamma = \left\{\gamma_i\right\}$.

Входным алфавитом $\Sigma$ машины Тюринга называется называется
подмножество элементов $\Gamma$ которыми оперирует головка $TM$,
т. е. те символы, которые она может распознать на ленте. Те символы,
которые головка не может распознать мы будем обозначать символом
$\beta$ (blank).

В процессе работы $TM$ она выполняет следующие действия:
\begin{itemize}
\item{считывает элемент на который указывает головка
  (см. рис. \ref{figAddAlgoTuring})}
\item{изменяет (или оставляет неизменным) этот символ на элемент
  $\sigma \in \Sigma \subset \Gamma$}
\item{изменяет положение головки на одну ячейку вправо ($R$) или влево
($L$)}
\end{itemize}

Изменение состояния $TM$ описывается таблицей переходов
$\Delta$. Элемент таблицы переходов записывается в следующем виде: 
$\delta_j\left(q_{old}, \gamma_{old}\right)$ где $q_{old} \in Q$ текущее состояние,
$\gamma_{old} \in \Gamma$ - выбранный элемент на ленте. Значение
перехода может быть 
не определено или записано в виде $\left\{q_{new}, \gamma_{new}, d\right\}$, где
$q_{new} \in Q$ - новое состояние машины Тюринга, $\gamma_{new} \in \Gamma$ -
новое значение элемента на ленте на который указывала головка,
т. е. $\gamma_{old}$ заменяется на $\gamma_{new}$. $d \in D =
\left\{L, R\right\}$ - направление
движения головки ($L$ налево, $R$ направо). В случае неопределенного
перехода говорят, что машина Тюринга зависла (halt) в состоянии $q_{old}$.



{'fraction_non_alphanumeric': 0.11141181777176365, 'fraction_numerical': 0.0009021199819576004, 'mean_word_length': 4.678617157490397, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2189069', 'n_tokens_mistral': 1817, 'n_tokens_neox': 2152, 'n_words': 550}