Делать языки в $ \ mathsf {Core} \ setminus \ mathsf {r} $ @ Turing Machines?

Question

Что мы можем сказать о языках в $ \ mathsf {Core} \ setminus \ mathsf {r} $ ?На этих языках есть Turging Machines?

Я знаю, что $ \ uverline {hp} \ in \ mathsf {Core} $ нет, не имеет Turging Machine, а также, что весь язык, который делаетУ Turing Machines находятся в $ \ mathsf {Re} $ , так правда ли, что для любого языка, который находится в $ \mathsf {Core} \ setminus \ mathsf {r} $ нет трюма?Интересно, почему это так, может кто-то уточнить?

Answer 1

Мы можем связать язык на машину Turging несколькими способами.

Если Turging Machine останавливает на всех входах, то язык принял на Turging Machine состоит из всех слов, которые приводят к тому, что машина для остановки в принимающемся состоянии. Класс $ \ mathsf {r} $ состоит из всех языков, которые принимаются некоторыми Turging Machine.

Для произвольной машины Tuging язык распознал на машине Turging, состоит из всех слов, которые вызывают остановку Turging Turging (в любом состоянии). Класс $ \ mathsf {Re} $ состоит из всех языков, которые распознаются некоторыми Turging Machine.

Если $ l \ in \ mathsf {core} \ setminus \ mathsf {r} $ , затем в частности, $ L \ notin \ mathsf {r} $ , и поэтому нет Turing Machine не принимает $ l $ . Если $ l $ были распознаны некоторыми Turging Machine, то $ l \ in \ mathsf {Re} $ . Однако это невозможно, с тех пор $ l \ in \ mathsf {Re} \ cap \ mathsf {r}=mathsf {r} $ .

Answer 2

Позвольте мне расширить на первом предложении youval Fileus 'Ответ:

Мы можем связать язык на машину Turging несколькими способами.

Ювал упоминает два: Приемное устройство (которое характеризует $ \ mathsf {r} $ ) и распознавание ( которые характеризуются $ \ mathsf {Re} $ ). Есть другие, однако. Наиболее очевидно, мы могли бы рассмотреть вопрос о «признании», - говорите, что Turging Machine $ m $ "Co-распознает" Язык $ L $ Если строки в $ l $ имеются именно строки, на которые $ m $ делает не HALT. Тогда, конечно, совместно распознавание характеризует $ \ mathsf {Core} $ .

Однако это немного неестественно. Гораздо более естественным, на мой взгляд, является понятие предел вычислимости . Сформулировано в терминах натуральных чисел для простоты, это следующее:

Функция $ f: \ mathbb {n} \ prevarrow \ mathbb {n} $ iff Есть вычислимый Функция $ h: \ mathbb {n} ^ 2 \ prightArrow \ mathbb {n} $ такой, что $$ f (x )=lim_ {s \ prevarrow \ infty} h (x, s), $$ или точнее такое, что для всех $ x $ есть Некоторые $ n $ такое, что для всех $ s> n $ у нас есть $ h (x, s)= f (x) $ .

a set $ x $ - это предел вычислимой, между тем, если IFF есть какой-то ограниченный вычислительную функцию $ x={i: f (i)= 1 \} $ . (Есть много других эквивалентных составов этого.)

Оказывается, что предел вычислимости имеет очень приятную альтернативную характеристику:

(SHOENFIELD) Функция $ f $ - это ограничение, вычислимая IFF. Это вычислимо относительно Проблема остановки $ \ Edityset '$ .

(и через post Мы получим другую характеристику с точки зрения «сложности определения. ")

Конечно, это включает в себя как $ \ mathsf {Re} $ и $ \ mathsf {Core} $ И гораздо больше, кроме: есть наборы, вычислимые относительно задачи остановки, которые не являются эквивалентными для любого набора в $ \ mathsf {Re} $ . (Это трудно доказать!)

и есть еще больше способов назначать языки наборы; Например, мы можем говорить о «ограниченном признаке» (что заключается в том, чтобы ограничить вычислимость, поскольку узнаваемость заключается в принятии), что дает нам $ \ sigma ^ 0_2 $ Языки.