1
튜링 머신이 언어에 대해 존재한다면, 언어는 재귀 적으로 열거 될 수 있다는 것을 알고 있습니다. 따라서 언어에 대한 열거 절차가 있습니다. 그러나 언어가 중요하다면 TM이 있어야 함을 의미합니까?셀 수있는 모든 언어에 TM이 있습니까?
감사합니다.
A
답변
1
집합 Σ *은 셀 수있는 집합이므로 모든 하위 집합을 셀 수 있습니다. 즉, 모든 무한 언어가 재귀 적으로 열거 가능한 것은 아니지만, 특히 무한 언어가 계산 가능하다는 것을 의미합니다. 따라서 TM이 존재하지 않는 무한한 언어가 무한히 많습니다.
희망이 도움이됩니다.
이 질문은 프로그래밍이 아닌 계산 이론에 관한 주제이므로 다루지 않습니다. –