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

[realeugene]

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

КА являются только его отдельные компоненты (триггеры, регистры и т.д.).

Один клоковый домен цифровой схемы проектируется обычно как сложный конечный автомат. Но и это не всегда. Два - уже одним автоматом не представимо. И тогда опять приходится предпринимать много усилий, чтобы где-нибудь в глубине программы начинающего студента его написанный на языке высокого уровня автомат работал так, как предсказывает преподаватель.

[b4b5]

В общем. Рассматриваем конечные последовательности, с возможностью неограниченного пополнения (добавления) памяти путем реализации этого механизма с помощью ДКА и на основе ДКА.
Рассматриваем неограниченные конечные последовательности конечных автоматов.
Аналогично доказательству бесконечности простых чисел.
И в целом, в математике любят рассматривать последовательности всякого рода от частичных сумм до иных величин.

Про неэквивалентность соответствующих определений я в курсе, в курсе.
Я не прошу вас предъявить бесконечную ленту.

-- 10.04.2025, 15:58 --

Поиск по форуму принес комментарий post924732.html#p924732

epros в сообщении #924732 писал(а):

Sonic86 в сообщении #924718 писал(а):

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

Если Вам так хочется, то это нетрудно сделать вполне очевидным образом. Назовём «автоматом» систему, возможные состояния которой составляют множество $X$, причём определена функция $f \, : \, X \mapsto X$, такая что состояние в следующий момент дискретного времени выражается через состояние в предыдущий момент следующим образом: $x_{i+1} = f(x_i)$.

Назовём автомат «конечным», если множество $X$ конечно. Машина Тьюринга, очевидно, является автоматом, но не конечным, в силу бесконечности количества состояний ленты.

Sonic86 в сообщении #924718 писал(а):

Это Вы сейчас утверждаете, что существует такое достаточно большое $n$, что я не смогу определить, принадлежит ли $a^nb^n$ языку $\{x: x=a^kb^k , k\in\mathbb{N}\}$? Неее...

Я готов даже утверждать, что существует такое достаточно большое $n$, что Вы не сможете определить, что оно существует. Имеется в виду — без привлечения компьютера себе в помощь.

[realeugene]

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

Рассматриваем неограниченные конечные последовательности конечных автоматов.

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

Ваша ошибка в непонимании разницы между конечными и счётными множествами.