Рубрики

Разрешимость и неразрешимость в TOC

Определение языков (или проблем *) как разрешимых, неразрешимых или частично разрешимых является очень распространенным вопросом в GATE. С правильными знаниями и достаточным опытом этот вопрос становится очень легко решить.

Начнем с некоторых определений:

Разрешимый язык. Решение проблемы P называется разрешимым (т. Е. Имеет алгоритм).
если язык L всех экземпляров yes для P разрешим.
Пример- (I) (проблема принятия для DFA). При условии, что DFA принимает данное
слово?

(II) (Проблема пустоты для DFA) Принимая во внимание DFA, оно принимает какое-либо слово?

(III) (проблема эквивалентности ДФА). Учитывая два ДФА, принимают ли они
тот же язык?

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

Частично разрешимый или полуразрешимый язык — Проблема решения P называется полуразрешимой (т.е. имеет полуалгоритм ), если языком L всех экземпляров yes для P является RE. Язык 'L' частично разрешим, если 'L' является RE, но не языком REC.

Рекурсивный язык (REC) . Язык 'L' называется рекурсивным, если существует машина Тьюринга, которая будет принимать все строки в 'L' и отклонять все строки не в 'L'. Машина Тьюринга будет останавливаться каждый раз и давать ответ (принятый или отклоненный) для каждого ввода строки. Язык 'L' разрешим, если это рекурсивный язык. Все разрешимые языки являются рекурсивными языками и наоборот.

Рекурсивно перечислимый язык (RE). Говорят, что язык 'L' является рекурсивно перечислимым языком, если существует машина Тьюринга, которая будет принимать (и, следовательно, останавливать) все входные строки, которые находятся в 'L', но могут иметь или не иметь остановка для всех входных строк, которые не находятся в «L». По определению, все языки REC также являются языками RE, но не все языки RE являются языками REC.

Теперь давайте решим несколько примеров —

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

Если мы можем свести уже известную неразрешимую проблему P1 к данной проблеме P2, то мы можем с уверенностью сказать, что P2 также неразрешима. Если бы P2 был разрешимым, то P1 также был бы разрешимым, но это становится противоречием, потому что P1, как известно, неразрешимо.

Например,

1. Учитывая машину Тьюринга «M», нам нужно выяснить, достигается ли когда-либо состояние «Q», когда в «M» вводится строка «w». Эта проблема также известна как «проблема въезда в государство».

Теперь давайте попытаемся свести проблему остановки к проблеме вхождения в штат. А машина Тьюринга останавливается только при переходной функции? (ци, а) не определено. Измените каждую неопределенную функцию? (Qi, a) на? (Qi, a) = (Q, a, L или R). Обратите внимание, что состояние Q может быть достигнуто только после остановки машины Тьюринга.

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

2. Учитывая два регулярных языка L1 и L2, проблема заключается в том, чтобы найти, существует ли строка 'w' в L1 и L2, разрешимая проблема или нет.

Сначала мы создадим две машины Тьюринга TM1 и TM2, которые моделируют DFA языков L1 и L2 соответственно. Мы знаем, что DFA всегда останавливается, поэтому машина Тьюринга, имитирующая DFA, также всегда останавливается. Вводим строку 'w' в TM1 и TM2. Обе машины Тьюринга остановятся и дадут нам ответ. Мы можем подключить выходы машин Тьюринга к модифицированному вентилю «И», который выдаст «да», только когда обе машины Тьюринга ответят «да». В противном случае будет выведено «нет».

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

Есть много вопросов на эту тему. Универсального алгоритма для их решения не существует. Большинство вопросов требуют уникальных и оригинальных доказательств. Здесь нужен опыт. Решая многие из этих проблем, можно очень быстро найти доказательства этих проблем на месте. Итак, продолжайте практиковаться.

* Слова «язык» и «проблема» могут использоваться как синонимы в теории вычислений. Например, «Проблема остановки» также может быть записана как «L = {<M, w> | Машина Тьюринга 'M' останавливается на входе 'w'} '. Здесь «L» — это язык.

Эта статья предоставлена Нитишем Джоши .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Разрешимость и неразрешимость в TOC

0.00 (0%) 0 votes