L이 모든 언어 인 경우. L 재귀 적으로 열거 (computably 열거), 다음 파마 (L)되고 또한 재귀 적으로 열거하면 : 언어 파마 (L)는 L.순열로 닫히는 반복적으로 열거 가능한 (계산 가능하게 열거 가능한) 언어?
참 또는 거짓에서 단어의 모든 순열의 언어입니다.
이 질문은 L이 결정할 수있는 경우 perms (L)과 같은 최종 결론에 도달했습니다.
나는 거짓이라고 말할 것이라고 생각하지만이 주장을 뒷받침 할 증거가 없습니다.
"재귀 적으로 열거 가능한"의미를 생각해보십시오. 즉, 언어에서 각 문자열을 쓰는 TM을 정의 할 수 있습니다. TM에 충분한 시간을 주면 결국 주어진 문자열을 쓰게됩니다.
언어의 주어진 문자열의 경우, 그것은 순열 수가 유한합니다. 튜링 기계는 문자열이 주어진다면 문자열의 모든 순열을 확실히 적어 둘 수 있습니다.
두 개의 튜링 기계를 함께 사용하는 것을 상상해보십시오. 첫 번째는 언어로 된 모든 문자열을 열거하고 두 번째 튜링 기계는이 문자열 각각의 모든 순열을 방출합니다. 결과는 첫 번째 언어로 된 문자열의 모든 순열을 열거합니다.
위에서 설명한 Turing Machine의 조합으로 새로운 Turing Machine이 생성됩니다. 따라서 우리는 원하는 언어의 모든 문자열을 열거하는 Turing Machine을 보유하고 있습니다. 정의에 따르면이 언어는 재귀 적으로 열거 가능합니다.