모든 무한 언어가 결정 불가능합니까?

Question

나는 무한한 언어가 모두 결정 불가능한가?

무한한 언어를 결정하려고하는 TM이 영원히 반복 될 것이기 때문에 TM은 결정자가 아닌 기억 장치가됩니다.

감사합니다.

Answer 1

아니요, 결정할 수있는 수많은 무한한 언어가 있습니다. 한 가지 간단한 예는 언어 {n € N | a^n}입니다. 즉 문자 "a"만 포함 된 단어의 언어입니다. 이 언어는 정규식 a*으로 일치시킬 수 있습니다. 그래서 그것은 정규 언어이며 따라서 결정할 수 있습니다.

Answer 2

sepp2k가 지적한 것처럼 a*은 일반적인 언어이므로 결정할 수 있습니다.

모든 유한 언어는 규칙적입니다. 일부 무한 언어는 규칙적입니다. 무한한 언어 만이 결정할 수 없습니다.

해결할 수 없으므로 언어에서 TM이 실패하는 개별 문자열이 있어야합니다. 실제로, 그러한 문자열이 무한히 많아야합니다 (그렇지 않은 경우 제대로 작동하지 않는 문자열은 특수한 경우 논리로 처리 할 수 ​​있습니다).

따라서 언어가 무한하다는 것은 결정적이지는 않지만 충분하지는 않습니다.