Моделирование конечного куска ленты машины Тьюринга

[realeugene]

b4b5 в сообщении #1681358 писал(а):

Кусок ленты длиной 5 - часть ленты помеченная единицами этой МТ.

У машины, переходы автомата которой не зависят от входа, ОК.
В любом случае, если приходится догадываться, что подразумевал автор - это не есть "точное математическое определение".

[juna]

b4b5 в сообщении #1681343 писал(а):

Я спросил тут http://dxdy.ru/post1681312.html#p1681312
"Конечный кусок ленты машины Тьюринга мы можем моделировать конечным автоматом?"
Пока ответа на данный элементарный вопрос не услышал.

Наверное потому, что нужно корректно формулировать вопрос. Что понимается под моделированием? Мы должны за Вас это додумать?
Конечные автоматы используются для распознавания предложений регулярных формальных языков, например, $S\rightarrow a | aS$. Считается, что цепочка символов распознается автоматом, если по ее окончанию, автомат находится в одном из конечных состояний. Вот в вашем примере на ленте напечатано пять единиц. По предложенной грамматике автомат может распознавать цепочки языка $L = \{a^n|n\geq 1\}$, т.е. произвольной фиксированной длины.
Для МТ считается, что по окончанию ее работы на ленте содержится результат. При ограничении длины ленты Вы не сможете записать на ленте цепочки произвольной фиксированной длины, а значит конечному автомату такая МТ эквивалентна быть не может.

[b4b5]

Одна ячейка ленты моделируется (имитируется) одним конечным автоматом, конечный набор автоматов будет имитировать конечный кусок ленты, бесконечный набор ДКА будет имитировать бесконечную ленту. Можно фрагменты ленты по N ячеек моделировать.
Сам блок управления МТ, тоже моделируется ДКА.
Отмерять конечный фрагмент ленты тоже легко, если требуется, ввели два спецсимвола, левый граница и правая граница.
Если вылезла МТ за границы меток, то "останов", переполнение памяти.
Можно предусмотреть механизм пополнения памяти. )

[realeugene]

b4b5 в сообщении #1681391 писал(а):

Сам блок управления МТ, тоже моделируется ДКА.

Собственно из этой фразы и следует, что вы не знакомы с машиной Тьюринга: её "блок управления" и есть конечный автомат по определению.

Тем более вы не знакомы с теорией вычислимости, к ведению которой относятся затронутые вопросы. И наверняка просто не слышали про проблему остановки. В форуме заниматься вашим образованием смысле нет: это слишком объёмный материал. Книжка Булоса и Джеффри, на которую я давал ссылку, хороша, почитайте.

[mihaild]

realeugene в сообщении #1681393 писал(а):

её "блок управления" и есть конечный автомат по определению

Только всё же не автомат, а трансдьюсер. У автомата весь "выход" - конечное состояние (принимающее или нет), а головка МТ обладает внутренним состоянием из конечного множества, и выдает символы алфавита (и движения) на каждом шаге.

[realeugene]

mihaild в сообщении #1681397 писал(а):

Только всё же не автомат, а трансдьюсер. У автомата весь "выход" - конечное состояние (принимающее или нет), а головка МТ обладает внутренним состоянием из конечного множества, и выдает символы алфавита (и движения) на каждом шаге.

Строго говоря, да, "конечный преобразователь", но очень часто, особенно, в инженерных приложениях, такое терминологическое различие не делают, продолжая называть конечный автомат с приписанными его дугам действиями конечным автоматом.

Upd:

Цитата:

Finite-state machines can be subdivided into acceptors, classifiers, transducers and sequencers.[6]

https://en.wikipedia.org/wiki/Finite-state_machine

[b4b5]

И получаем, что конечная композиция конечных автоматов, часть которых используется в качестве конечного фрагмента ленты МТ в состоянии моделировать работу конкретной МТ, которая может работать на конечном фрагменте ленты.

[realeugene]

b4b5 в сообщении #1681487 писал(а):

И получаем, что конечная композиция конечных автоматов, часть которых используется в качестве конечного фрагмента ленты МТ в состоянии моделировать работу конкретной МТ, которая может работать на конечном фрагменте ленты.

Некоторые Машины Тьюринга допускают те же языки, что и конечные автоматы. Но далеко не все. Самое интересное начинается с языками, для которых существует подходящая МТ, но не конечный автомат. Причём, то, что ни один такой конечный автомат не может существовать (в силу конечности множества его состояний) легко доказывается.

[b4b5]

Добавляем механизм (алгоритм) увеличения размеров памяти аналогичный страничной организации памяти при достижении помеченных границ (при исчерпании свободной доступной памяти) моделируемой машины Тьюринга. Создаем еще ДКА и добавляем в качестве памяти.
Таким образом получаем неограниченно расширяемую память.
Все в точности как у реальных физических конечных автоматов (человека или компьютера).

-- 08.04.2025, 17:58 --

b4b5 в сообщении #1680942 писал(а):

Человек вполне себе конечный автомат, моделирует не только арифметику, но и машину Тьюринга.
Потенциально бесконечную память и моделируем.

О чем я сразу и сказал.

[mihaild]

b4b5 в сообщении #1681509 писал(а):

Добавляем механизм (алгоритм) увеличения размеров памяти аналогичный страничной организации памяти при достижении помеченных границ (при исчерпании свободной доступной памяти) моделируемой машины Тьюринга

И не в лотерею, а в преферанс. И не выиграл, а проиграл.

[b4b5]

Конкретнее, если есть что сказать.

-- 08.04.2025, 21:34 --

Возможно, стоит понять почему человека можем в математическом смысле называть конечным автоматом.

[juna]

b4b5 в сообщении #1681525 писал(а):

Конкретнее, если есть что сказать.

А вот я бы обратился к Вам с таким вопросом. Что конкретно Вы хотите сообщить. Пока только неформализованные рассуждения, противоречащие принятым определениям МТ и КА.

-- Вт апр 08, 2025 21:40:06 --

b4b5 в сообщении #1681525 писал(а):

стоит понять почему человека можем в математическом смысле называть конечным автоматом.

И почему же?

[b4b5]

juna Я не помню уже как именно ввязался в дискуссию про свободу воли, тему отделили и связь сложно найти, да и смысла нет.
У меня нет ни одного утверждения противоречащего теории.
А тезисы уже привел выше http://dxdy.ru/post1680942.html#p1680942

juna в сообщении #1681526 писал(а):

И почему же?

А как вы считаете, обычный компьютер является конечным автоматом?

[mihaild]

b4b5 в сообщении #1681528 писал(а):

У меня нет ни одного утверждения противоречащего теории.

b4b5 в сообщении #1680942 писал(а):

Человек вполне себе конечный автомат, моделирует не только арифметику, но и машину Тьюринга

Хорошо известно, что в общепринятом смысле понятия "моделирует", конечные автоматы МТ моделировать не могут. А именно, существуют языки, распознаваемые некоторой МТ, но не распознаваемые никаким конечным автоматом.

[juna]

b4b5 в сообщении #1681528 писал(а):

У меня нет ни одного утверждения противоречащего теории.

Какой именно теории, о моделировании машины Тьюринга конечными автоматами?
У машины Тьюринга есть внешняя память - лента и позиция на ленте (можно просто задать строкой слева и строкой справа от пустых символов), внутренняя память - состояния МТ, движение по ленте и печать на ленте (меняет строку слева и справа), что определяется считанным из внешней памяти символом и внутренним состоянием.
Конечный автомат (распознаватель) - это

$$A=<Q, \Sigma, \delta, q_0, F>$$

$Q$ - конечное множество состояний автомата.

$\Sigma$ - конечное множество входных символов (алфавит автомата).

$\delta$ - функция перехода из одного состояния в другое состояние под действием символа из $\Sigma$, $\delta: Q\times \Sigma\rightarrow Q$

$q_0$ - начальное состояние автомата, в котором он находится перед началом работы $q_0\in Q$.

$F$ - непустое множество конечных состояний автомата, в которых он должен находиться по окончанию работы $F\subseteq Q, F\neq \emptyset$

Вот и покажите формально, как "смоделировать" вышеперечисленные компоненты МТ.

b4b5 в сообщении #1681528 писал(а):

А как вы считаете, обычный компьютер является конечным автоматом?

Я считаю это фигурой речи. КА являются только его отдельные компоненты (триггеры, регистры и т.д.). А уж отождествлять человека с конечным автоматом, совсем несерьезно.