LH에서 L로의 감소를 맵핑 할 수있는 경우 L이 R이면 L이 될 수 있습니다.

Question

나는 언어의 수단을 의미하는 것을 정확하게 이해하지 못하는 것으로 보인다.

예를 들어 LM이라는 언어가 있음을 알려줍니다.

LM이 재귀인지 여부를보고 싶습니다. 그렇지 않으면 L-halting 문제로부터 LM으로의 감소를 찾으십시오.

LM이 재귀 적이므로 L-halting 문제가 재귀적이고, 물론 LM은 재귀 적이 아닙니다.

그러나 LM이 LM에서 LM까지 줄이는 방법을 발견했기 때문에 LM이 다시 말할 수 있습니까? LM이 다시 있음을 어떻게 보여줄 수 있습니까?

Answer 1

오해가 발생할 수있는 많은 동등한 / 유사한 정의가 있기 때문에 조금 일을 분명히합니다.

• 언어 $ l $ 은 재귀 함수 $ \ chi_l $ (또는 튜링 머신 또는 다른 해당 계산 모델), 즉 $$ \ chi_l (x)=begin {사례} 1 & \ quad; x \\ 0 & \ quad; \ 텍스트 {OTW}. \ end {사례} $$ $ \ chi_l $ 을 모든 입력에 대해 정의해야합니다.

• 해당 언어 $ l $ 은 재귀 적이 아니며 비가 아닌 "감소"를 찾아서 - 그것에 대한 회전 언어. 이것은 아마도 감소로 의미하는 바이트이며, 다음과 같이 정의됩니다.

  우리는 $ a $ 은 언어 $ b $ 에 튜닝 가능하다고 말합니다. $ a $ < "를 결정하는 재귀 함수 (또는 튜링 머신)를 구성 할 수있는 경우 $ a \ le_t b $ / span> $ b $ 에 대한 기능이 있음을 가정합니다.

  정의로 보이기 때문에 $ b $ 에서 $ a $ .

  $ a $ 및 $ b $ $ a \ leq_t b $ $ b $ 은 재귀적이고, 그렇다면 $ a $ .

  $ a $ 은 재귀 적이 아니며, 감소 $ a \ leq_t b $ B $ 에 대해 $ 은 재귀 적으로 만들어줍니다.

• 언어 $ l $ 은 remang $ \ varphi_l $ \ span 클래스="수학 컨테이너 "> $ DOM (\ varphi_l)= l $ (또는 그것을 켜고 / 받아들이며 멈춤). 예를 들면 예를 들면 $$ \ varphi_l (x)=begin {사례} 1 & \ quad; x \\ \ \ uparrow & \ quad; \ text {otw.} \ end {사례} $$

  여기서 $ \ uparrow $ 은 "정의되지 않음"(또는 "정지하지 않음")을 의미합니다. 이름이 익숙해지는 "열거 가능성"과 같은 재설정의 다른 정의가 있습니다. 이는이 하나의 것과 같습니다.

• 그러나 언어 $ l $ 은 재, 폐쇄 감소가 필요하지 않기 때문에 감소가 도움이되지 않습니다. 다시 네스 전송. 예를 들어 $ \ {halt}} \ leq_t l_ {halt} $ \ / span> (실제로 어떤 언어는 보완에 딱딱 할 수 없으며 그 반대의 경우도 마찬가지 다수)을 관찰합니다. 그러나 $ l_ {halt} $ 은 $ \ {halt}} $ 은 아닙니다.

  그러나 다른 종류의 강한 reduction이 전송되는 감소가 있습니다. 그러한 감소 중 하나는 "다중 - 하나의 재건"이라고합니다.

  언어 $ a $ 은 언어 $ b $ , $ a \ leq_m b $ $ f $ 이있는 경우 모든 입력 $ x $ $$ x \ \ IFF F (x) \ b $$

  $ a \ leq_m b $ 은 강력한 감소입니다. $ a \ leq_t b $ (반대로 반대의 경우는 아닙니다). 그래서, 튜링 감소와 마찬가지로 재발력을 전송합니다. 우리는 또한

  가 있습니다

  $ a $ 및 $ b $ $ a \ leq_m b $ $ b $ 이 다시, $ a $ .

  이것이 어떻게 진실인지 확인하려면 $ \ varphi_a (x)=varphi_b (f (x) $

  언어 $ B $ 을 보여주는 올바른 방법은 하나의 감소 $ a $ 의 경우. $ \ {halt}} \ nLeq_m l_ {halt} $

$ \ overline

더 읽기를 위해

l="nofollow noreferrrer"> 계산성 이론 s.Barry Cooper pt.나는 ch.7.