пример языка, который может быть распознан ТМ, но не может быть определен ТМ
Будет ли ответ:
TM={<M,w> M is a TM that accepts input string w}
Могу ли я ошибаться?
Короче говоря, любая строка, распознаваемая ТМ, называется распознаваемой ТМ, тогда как любые строки, приемлемые ТМ, называются разрешимыми ТМ.
Что касается вашего первого вопроса: существует ли язык, который распознается ТМ, но не разрешается ТМ? - ответ "да", и указанный вами язык, являющийся универсальным языком, является примером такого языка.
Что касается вашего второго вопроса - в чем разница между разрешимостью и узнаваемостью? - ответ, который вы дали, находится на правильном пути, но, как написано, как неправильный. Помните, что разрешимость и узнаваемость являются свойствами языков, а не строк. Не существует таких вещей, как «разрешимая строка» или «распознаваемая строка».
Язык L разрешим, если существует ТМ M со следующими свойствами: для каждой строки w L M принимает w, а для каждой строки w L M отвергает w. Другими словами, если вы не знаете, находится ли w в L или нет, вы можете запустить M на w, подождать, пока он даст вам ответ, и найти ответ.
Язык L распознаваем, если существует ТМ M со следующими свойствами: для каждой строки w L M допускает w, а для каждой строки w L M не допускает w (то есть либо M зацикливается на w, либо M отвергает w). ж). Другими словами, если вы уверены, что w L и хотите подтвердить это, вы можете запустить M на w, посмотреть, как он примет w, и убедиться, что ваш ответ был правильным, но если вы не знали заранее, является ли w в L вы, возможно, не сможете использовать M, чтобы узнать ответ, так как M может зацикливаться на w.
