Язык, разрешимый по Тьюрингу, и машина, разрешимая по Тьюрингу.разница?

Question

У меня есть машина Тьюринга М, и я доказал, что М не является решающим фактором.Затем я доказал, что A = L (M) или что язык A, который распознает M.Теперь меня спросили «Является ли язык (A) разрешимым по Тьюрингу?»

Мой вопрос таков: если я уже доказал, что M не является решающим, могу ли я использовать это, чтобы подразумевать, что язык (A) не является ли Тьюринг-разрешимым?На мой взгляд, язык для машины M будет состоять из не только принятых языков, но и бесконечных длинных строк, которые никогда не останавливаются.Это сделало бы язык также не разрешимым по Тьюрингу?

Спасибо за любой совет.

Answer 1

Я думаю, что в этом вопросе есть некоторые неясности, которые следует уточнить.Чтобы быть на той же странице, позвольте мне уточнить некоторые определения: Определения

1. Формальный язык L называется «разрешимым по Тьюрингу», если для него существует «решающий».
2. "Decider" - это TM, который останавливается на всех строках сигма-звезды (Sigma - алфавит этой TM).Точнее говоря, когда мы вводим строки из L (что должно быть принято) или из L-бара (что должно быть отклонено), машина останавливается.Обратите внимание, что все эти строки принадлежат Сигме-звезде.Нам не разрешено вводить строки за пределами сигма-звезды.
3. «Строка» - это конечная последовательность символов из алфавита.Поэтому в вашем вопросе: «... бесконечные длинные строки ...» - это недопустимое утверждение в формальных языках, потому что строки должны быть конечными.

Итак, когда вы говорите, вы доказалиM не является решающим фактором, это означает, что вы доказали, что M попадает в бесконечный цикл для «хотя бы одной строки сигма-звезды».Эта строка может быть в наборе A или A-bar.

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

Теперь, основываясь на этом разъяснении, если вы получили свой ответ, этоотлично, но если нет, не могли бы вы перефразировать ваш вопрос более точно.