Алгоритм деления пополам для произвольной булевой функции

[involume]

Цель в том и состоит чтобы выяснить, как это записать.

[nikvic]

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

[arseniiv]

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

[involume]

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

[nikvic]

Что значит попросили? Курсовая? Где?
Испросите разрешения воспользоваться теоремами композиции и т.п.

[involume]

Да, курсовая. Теоремами этими можно пользоваться.

[involume]

Вопрос такой. У меня есть лента МТ, я переписываю её на вторую ленту, то есть получается две одинаковые ленты. Как с помощью состояний МТ сделать так, чтобы мы нашли середину у этих лент. То есть допустим если мы идём слева одной ленты, а у другой справа. Если есть 1 или 0, то вместо них записываем пустой символ. Так вот, собственно такой алгоритм полностью сотрёт две ленты и оставит лямбда, как этого избежать?

[arseniiv]

А не проще будет записывать на вторую просто единицы, а потом разделить число пополам? После этого нужное отшагать по первой.

[nikvic]

involume в сообщении #699494 писал(а):

Вопрос такой. У меня есть лента МТ, я переписываю её на вторую ленту,

Не очень понятны ограничения задачи. Две ленты, 3 буквы внешнего алфавита?
"Пустышку" можно использовать как дополнительные буквы, организуя слова из пустышек между двумя единичками (или ноль - один, как скобки).

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

involume в сообщении #669773 писал(а):

1. Сравниваем соседние биты пары, затираем пару. Формируем справа
строки из первых (q1) и вторых (q2) эл-в пар (Q1 и Q2 соответственно).
Повторяем до тех пор пока не сотрем исходную строку значений с ленты или пока не встретится пара с отношением q1>q2, во втором случае функция не монотонна.
2. Склеиваем получившиеся строки Q1 и Q2. Переходим к 1 шагу
алгоритма. Цикл повторяется N раз, где N число аргументов функции.
3. Если цикл выполняется N раз ф-ция монотонна.

Теперь это надо как-то в виде состояний записать вида q a -> q b D

involume, наберите формулы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

[involume]

У нас алфавит из ${0,1}$, сама проблема в том, как с помощью состояний описать процесс деления 1 ленты пополам. Было предположение на счёт этого, но видимо оно не правильное:
$q_f (0,0) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (0,1) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (1,0) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (1,1) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (lambda,0) \to q_p (lamdba,0) (L,S) \kill$
$q_f (lambda,1) \to q_p (lamdba,1) (L,S) \kill$
$q_f (0,lambda) \to q_p (0,lamdba) (S,R) \kill$
$q_f (1,lambda) \to q_p (1,lamdba) (S,R) \kill$
Это как раз описанный мой алгоритм с двумя лентами, когда мы начинаем двигаться с двух разных сторон и записывать вместо 1 или 0 лямбда.

[arseniiv]

Может, лучше \lambda $\lambda$?

[involume]

Цитата:

Может, лучше \lambda $\lambda$?

Какая разница, как я это написал, лучше бы предложили мысль хоть какую-то по этому поводу.

[nikvic]

Уже предложена - для начала расширьте внешний алфавит, а потом "конвертируйте" в старый.