인식 또는 공동 튜링이 인식 튜링된다확인이 있는지 여부 언어 나는이 두 언어가
A = {<M> | M is a TM and L(M) contains exactly n strings }
B = {<N> | N is a TM and L(N) contains more than n strings }
나는이 둘은 결정 불가능하다고 생각하지만, 그들이 인식 또는 공동 튜링이 인식 튜링 여부를 나는 확실하지 않다 .
B은 가능한 모든 입력 테이프에 M의 실행을 인터리브 할 수 있으므로 튜링을 인식 할 수 있습니다. 실행중인 M 인스턴스 중 n 이상이 halt-accept 인 경우 halt-accept.
언어가 B' = {<N> | N is a TM and L(N) contains no more than n strings } 인 경우 Turing 인식 할 수 없기 때문에 Turing 인식 할 수 없다는 것을 알고 있습니다 (1, 2, ..., n에 대한 인식기의 실행을 인터리빙하고 halt-accept if 그 중 누구든지). 이는 B'이 공감할 수 있어야하기 때문에 B과 B'을 결정할 수 있음을 암시합니다.
A이 공존 할 수있는 경우 n과 다른 문자열을 허용하는 시스템을 인식 할 수 있습니다. 특히 n = 1으로 지정하십시오. 가능한 모든 문자열 w에 대해 L(M) \ {w}을 허용하도록 구성된 TM에서 n 문자열 이외의 언어를 포함하는 시스템에 대해 인식기를 실행할 수 있습니다. 각 단계에서 모든 기존 시스템의 한 단계를 실행 한 다음 새 시스템을 구성하고 반복함으로써 실행을 인터리빙하고 모든 TM이 결국 여러 단계로 임의로 실행되도록합니다.
|L(M)| = 1으로 가정하면이 TM 중 하나는 정확히 받아들입니다 (L(M)에서 유일한 문자열을 제거하는 것) 나머지는 중단되거나 영구히 실행됩니다. 따라서 |L(M)| != 1의 인식자를 사용하여 |L(M)| = 1의 인식자를 구성 할 수 있습니다. 이는 k 입력 문자열의 가능한 모든 집합을 뺀 값을 |L(M)| != k 및 |L(M)| = k으로 일반화합니다.
따라서 A가 공감할 수있는 튜링이라면 Turing도 인식 할 수 있고 따라서 결정할 수 있습니다. 우리는 그것이 틀렸다는 것을 이미 알고 있습니다. 따라서 우리는 A가 공감할만한 Turing인지를 알아 내야합니다. 그것도 Turing을 인식 할 수있는 것이 아닙니다.