0
голосов
0
ответов
75 показов

Пример:$$ X = \alpha X + \beta Y + \delta $$$$ Y = \gamma X + \mu Y + \epsilon $$Из первого:$$ X = a^{\ast} (\beta Y + \delta) $$подставляем во второе ...
0
голосов
0
ответов
44 показа

Постройте бескванторную формулу в в модели (R, 0, 1, <, =, +, *) с параметрами p, q, которая эквивалентна существованию кратного действительного ко ...
0
голосов
0
ответов
55 показов

Разрешимо ли множество описаний МТ, которые на любом входном слове w работают недольше, чем |w| тактов?
0
голосов
0
ответов
45 показов

Постройте m-сводимость множества описаний машин Тьюринга, останавливающихся на входе 0, к множеству описаний машин Тьюринга, не останавливающихся на в ...
2
голоса
0
ответов
79 показов

Разрешимо ли множество описаний машин Тьюринга, которые вычисляют тождественную функцию? (т.е. на любом входе такая машина даёт результат, равный вход ...
0
голосов
0
ответов
52 показа

Разрешимо ли множество описаний Машин Тьюринга, которые на любом входном слове w работают недольше, чем |w| тактов?
0
голосов
0
ответов
43 показа

Разрешимо ли множество описаний таких Машин Тьюринга, которые при работе на пустом входе проходят через каждую ячейку не более пяти раз?
0
голосов
0
ответов
222 показа

Формулы первого порядка с предикатными символами $%B(x), P(x, y)$% будем интерпретировать на непустых словах в алфавите $%\{0, 1\}$% так: переменные ф ...
1
голос
0
ответов
74 показа

Доказать, что существует язык L, для которого не существует машины Тьюринга, которая бы принимала на вход два слова, разделенных символом-разделителем ...
0
голосов
1
ответ
91 показ

Построить грамматику для языка L={w∈{a,b}*:|w|_a > 2|w|_b} (интересно как правильно задать правила, чтобы ничего не упустить)
1
голос
1
ответ
80 показов

Докажите, что язык L={a^ib^j: i,j∈N, НОД(i,j)=1} является нерегулярным.
0
голосов
0
ответов
76 показов

Какие из слов могут стать формулами логики первогопорядка после добавления пропущенных скобок и подходящем понимании входящих в них букв латинского ал ...
0
голосов
1
ответ
107 показов

Существует ли интерпретация, в которой(a) ложна формула(∀xU(f(f(f(x))))) ∧ (∃x¬U(f(f(f(f(x))))))?(b) истинна формула(∃xU(f(f(f(x))))) ∧ (∀x¬U(f(f(f(f( ...
0
голосов
0
ответов
86 показов

Множество формул Г таково, что Г ⊢ z, где z – переменная. Следует ли из этого, что что какая-то формула в Г содержит переменную z?
0
голосов
0
ответов
68 показов

Пусть Г ⋃ {A} ⊢ B за n шагов. Оценить сверху число шагов вывода Г ⊢ А → В.
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru