- 22, Oct 2024
- #1
Заявление о вызове
Целью этого задания является построение 5-го штата. Бесконечная машина Тьюринга это занимает больше всего времени, чтобы остановиться. Поскольку машины Тьюринга с бесконечным временем могут работать бесконечное время, ваш результат будет «трансфинитным порядковым номером».
Это постановка задачи, но если вы не понимаете, что все это значит, или хотите углубиться в детали, остальная часть этой задачи — это некоторые определения и примеры, которые помогут вам. Если вам что-то непонятно или не объяснено, оставляйте комментарии.
Машины Тьюринга
Для ясности мы определим машины Тьюринга, используемые для решения этой задачи. Это будет довольно формально. Если вы знакомы с машинами Тьюринга, это одноленточный, двоичный Машина Тьюринга без явного состояния остановки и с возможностью нет смены двигаться. Но для абсолютной ясности вот как мы определим классическую машину Тьюринга и ее исполнение:
Машина Тьюринга состоит из \$3\$-кортежа, содержащего следующее:
- \$Q\$: Конечный непустой набор состояний.
- \$q_s : Q\$: Начальное состояние.
- \$\delta : Q\times \{0,1\} \nrightarrow Q\times \{0,1\}\times\{1, 0, -1\}\$: частичная функция перехода, которая отображает состояние и двоичный символ, к состоянию, двоичному символу и направлению (влево, вправо или отсутствие движения).
Во время выполнения конкретной машины Тьюринга у машины есть состояние который представляет собой \$3\$-кортеж следующего:
- \$\xi_\alpha : \mathbb{Z}\rightarrow \{0,1\}\$: лента представлен функцией преобразования целого числа в двоичный символ.
- \$k_\alpha :\mathbb{Z}\$: Расположение считывающей головки.
- \$q_\alpha : Q\$: Текущее состояние.
Для машины Тьюринга переход Функция принимает состояние машины на шаге \$\alpha\$ и сообщает нам состояние машины на шаге \$\alpha + 1\$. Это делается с помощью функции перехода \$\delta\$. Вызываем функцию \$\delta\$ с текущим состоянием и символом под заголовком чтения:
\$
\delta\left(q_\alpha, \xi_\alpha\left(k_\alpha\right)\right) \$ Если это не дает результата, то считаем, что машина имеет
- остановлен
- на шаге \$\alpha\$, и условие остаётся прежним. Если это дает результат \$\left(q_\delta, s_\delta, m_\delta\right)\$, то новое состояние в \$\alpha+1\$ будет следующим:
- \$\xi_{\alpha+1}(k) = \begin{cases}s_\delta & k = k_\alpha \\ \xi_\alpha(k) & k \neq k_\alpha\end{cases}\ $ (То есть лента заменяет символ на считывающей головке символом, заданным \$\delta\$)
\$k_{\alpha+1} = k_\alpha+m_\delta\$ (то есть считывающая головка движется влево вправо или не движется вообще)
- \$q_{\alpha+1} = q_\delta\$ (то есть новое состояние — это состояние, заданное \$\delta\$)
- Дополнительно мы определяем состояние машины в момент времени \$0\$.
- \$\xi_0(k)=0\$ (в начале ленты все нули)
\$k_0=0\$ (считывающая головка начинается с нуля)
\$q_0=q_s\$ (Начать в исходном состоянии)
Таким образом, по индукции определяется состояние машины Тьюринга для всех шагов, соответствующих натуральному числу.
Бесконечные ординалы В этом разделе я представлю концепцию трансфинитных ординалов в несколько неформальном контексте. Если вы хотите найти более формальное определение, это объяснение основано на определении ординалов фон Неймана..
В большинстве случаев, говоря о порядке событий, мы используем натуральные числа. Мы можем присваивать событиям номера, чтобы события с меньшими номерами происходили раньше. Однако в этой задаче нас будут интересовать события, которые происходят после бесконечного числа предыдущих событий, и для этого натуральные числа не подходят. Итак, мы представим
- бесконечные ординалы
- Для этого мы воспользуемся специальной функцией \$g\$. Функция \$g\$ принимает набор чисел и возвращает нам наименьшее число, большее, чем все числа в этом наборе. Для конечного набора натуральных чисел это максимум плюс 1. Однако эта функция не определена только для натуральных чисел. Например, что такое \$g(\mathbb{N})\$ или наименьшее число, большее всех натуральных чисел. Чтобы создать наши ординалы, мы говорим
\$0\$ существует и является порядковым номером.
Если \$X\$ — набор ординалов, то \$g(X)\$ существует и является ординалом.
\$
\begin{eqnarray} \omega\times 2 &=& \omega+\omega &=& g(\{\omega + x : x\in \mathbb{N}\})\\\omega^2 &=& \omega\times\omega &=& g(\{\omega \times x + y : x\in \mathbb{N}, y\in \mathbb{N}\})\\
\omega^3 &=& \omega\times\omega\times\omega &=& g(\{\omega^2\times x+\omega\times y + z : x\in \mathbb{N}, y\ в \mathbb{N}, z\in \mathbb{N}\})\\
\omega^\omega &=& & & g(\{\omega^x\times y + z : x\in \mathbb{N}, y\in \mathbb{N}, z < \omega^x\} )\\
\end{eqnarray} \$ Если порядковый номер не является преемником другого порядкового номера, то есть не существует следующего меньшего порядкового номера, мы называем этот порядковый номер
предел порядкового номера
. Например, \$\omega\$, \$\omega\times3\$ и \$\omega^{\omega\times 2}+\omega^6\times 4\$ — все это предельные порядковые номера. \$3\$, \$\omega\times 5 + 12\$ и \$\omega^{\omega^\omega}+1\$ — нет. Некоторые авторы далее уточняют, что 0 не является предельным порядковым номером; мы будем подробно говорить об 0, когда будем говорить о предельных порядковых числах, чтобы избежать путаницы.
- Бесконечные машины Тьюринга
Классическая машина Тьюринга оснащена стартовым статусом и способом перехода из одного состояния в другое. Это позволяет определить состояние машины на любом конечном шаге.
- Машины Тьюринга с бесконечным временем расширяют классические машины Тьюринга, чтобы иметь определенный ненулевой статус.
- ограничивать ординалы
- также. Это порядковые номера, определенные выше, которые не являются преемниками какого-либо предыдущего порядкового номера. Это дополнение делает состояние машины определяемым также и в трансфинитное время.
\$\$
Формальное определение
Для этого добавим в определение машины дополнительный объект
\$q_l : Q\$: Предельное состояние
И мы определяем состояние машины при некотором предельном ординале \$\lambda\$ как \$\xi_\lambda(k) = \limsup_{n\rightarrow \lambda} \xi_n(k)\$ \$k_n = 0\$
\$q_n = q_l\$
Пример
Здесь у нас есть диаграмма долго работающего автомата с двумя состояниями:
Если мы хотим подсчитать, сколько времени потребуется для остановки, мы не можем просто бросить это в компьютер и запустить, нам придется определить это вручную.
Для начала мы проследим за машиной через ее нормальное выполнение. Он начинается с \$q_1\$, и мы видим, что оттуда он
всегда
переходит к \$q_2\$, переворачивая ячейку под головкой чтения-записи. Так вот получается
ячейка включена.
Затем, поскольку ячейка включена, она вернется к \$q_1\$, отключив ячейку и переместившись вправо. Это ставит нас в то же самое состояние, что и в начале, за исключением того, что головка чтения-записи продвинулась на 1.
Таким образом, он будет продолжаться в этом цикле включения и выключения бита и бесконечного движения вправо.
Теперь, когда мы определили поведение машины на всех конечных шагах, мы можем выяснить состояние на шаге \$\omega\$.
![[алексей Филатов] Скрытые Внушения В Продажах И Коммуникациях](/assets/images/icons/forum0.png){kind=icon}
![[Приват]Аим по скину - абсолютно бепалевный](/assets/images/icons/forum2.png){kind=icon}