0
재귀 적으로 열거 가능한 언어를 인식 할 수 있고 기계를 돌려 재귀 언어를 사용할 수 있다고 할 때,이 두 용어의 차이점은 무엇입니까? 또한 TM Computable의 의미는 무엇입니까?오토 마타 이론의 수용성, 계산 가능성, 결정 가능성 및 인식 가능성의 차이점은 무엇입니까?
A
답변
1
언어는 수락하는 총 튜링 기계가있는 경우 재귀 적입니다. 즉, 튜링 기계 계산이 동일한 알파벳에 대한 모든 입력 단어에 대해 유한 함을 의미합니다. TM은 항상 중단되고 입력 단어를 수락하거나 거부합니다.
재귀 == 결정 가능.
언어를 인식하는 튜링 기계가 존재하는 경우, 언어는 재귀 적으로 열거 가능하다. 속성이 약합니다. TM은 해당 언어에 속한 단어를 수락하지만 언어가 아닌 단어의 경우 해당 단어를 거부하거나 반복 할 수 있습니다.
재귀 적 언어 집합은 재귀 적으로 열거 가능한 언어의 하위 집합이므로 모든 재귀 적 언어도 재귀 적으로 열거 가능합니다.
함수 f : N → N은 이진수 n을 입력으로하여 f (n)을 출력하는 튜링 기계가있는 경우 계산 가능합니다. 출력은 계산 후 테이프에 기록됩니다.
이것은 순수한 이론으로 나중에 강의 노트/책을 픽업하는 것이 가장 좋습니다.