저는이 두 가지의 차이를 이해하는 데 정말로 애 쓰고 있습니다. 내 교과서에서, 그것은 본질적으로는 튜링 - 인식 언어의 보완 인 경우 언어가 공동 튜링 인식 할Turing-Decidable과 Co-Turing-Decidable의 차이
을 말함으로써 그 차이를 설명합니다.
나는이 정의의 일부분을 이해할 수 없다 : 튜링 인식 언어의 보완어 란 무엇을 의미합니까?
다른 언어의 보완어인지 정확히 어떻게 결정합니까?
("Turing decidable"과 "co-Turing decidable"이라는 용어는 같은 것입니다. 그러나 "튜링 인식 가능"및 "공동 튜링 가능"은 동일하지 않습니다. 내 대답을 다루기로 결정했기 때문에 언어가 결정 가능하면 그 보체도 결정할 수 있어야합니다. 인식 할 수있는 언어는 아닙니다.
직관적으로 언어는 다음과 같습니다. 언어에 문자열이 주어지면 문자열이 실제로 언어 내에 있음을 확인할 수있는 컴퓨터 프로그램이 있으면 튜링 식으로 인식 할 수 있습니다. 이 프로그램은 문자열이 언어에 없으면 무한 루프 할 수 있지만 언어에 문자열을 입력하면 항상 허용됩니다.
언어가 Turing 인식 할 수있는 언어의 보완어 인 경우이 언어가 공동으로 인식 할 수있는 것은 사실이지만이 정의는 현재 무슨 일이 일어나고 있는지에 대해서는별로 알려주지 않습니다. 직관적으로, 언어가 함께 튜링 가능하다고 가정하면, 언어로 이 아니고이 아닌 문자열이 주어지면 결국 해당 문자열이 언어로되어 있지 않음을 확인하는 컴퓨터 프로그램이 있음을 의미합니다. 그러나 문자열이 실제로 언어 내에있는 경우 무한 루프 될 수 있습니다. 그 이유는 간단합니다. - 일부 문자열 w가 함께 공히 인식 가능한 언어에 포함되어 있지 않으면 그 문자열은 그 문자열을 정의 할 수있는 (co-Turing-recognizable) 언어의 보완 안에 포함시켜야합니다. 튜링으로 인식 할 수 있어야합니다. w가 튜링으로 인식 할 수있는 보완 요소이므로, w가 실제로 보완에 있음을 확인할 수있는 프로그램이 있어야합니다. 따라서이 프로그램은 w가 원래 튜닝 가능 언어라는 것을 확인할 수 있습니다.
요약하면 튜링 인식 기능이란 문자열 w가 언어로되어 있는지 확인할 수있는 프로그램이 있다는 의미이며, 동시 튜링 인식 기능이란 문자열 w가 이 아님을 확인할 수있는 프로그램이 있음을 의미합니다.을 언어로 사용하십시오.
희망이 도움이됩니다.
해당 언어의 문자열 만 중단하고 수락하는 튜링 기계가있는 경우 언어가 인식 가능하며 TM이 아닌 언어의 문자열 인 경우 TM은 거부하거나 전혀 중단하지 않습니다. 참고 : 언어가 아닌 문자열의 경우 Turing Machine이 중단되어야한다는 요구 사항은 없습니다.
언어로 문자열을 허용하고 언어가 아닌 문자열을 거부하는 튜링 기계가있는 경우 언어가 결정할 수 있습니다.
이 답변은 묻은 질문을 완전히 피하고 그냥 공식적인 정의를 내 렸습니다. 그는 그 질문을 이해하지 못하거나 피하지 않을 수 있습니다. –
이것은 대단히 도움이됩니다. 나는 실제 정의를 결정하는 것을 어렵게 만드는 생각하고있는 단어를 넣을 수 없었다. –
Downvoter-이 답이 무엇이 잘못되었는지 설명해 주시겠습니까? 가능한 한 유용하도록하고 싶습니다. 무엇이 잘못되었는지를 잘 모릅니다. – templatetypedef
@templatetypedef 나는 downvoter보다 이것에 대해 더 많이 알고 있다고 생각합니다. –