계산 모델을 배울 수 있는 좋은 자료가 있나요?

Question

호기심에서 나는 내가 작업하는 시스템이 어떤 계산 모델과 기능적으로 동등한지 확인하고 동등성을 증명하려고 노력하고 있습니다.이 문제에 더 오랜 시간을 투자할수록 시스템이 Turing과 동일하지 않다고 의심됩니다.Turing Machines와 재귀적으로 열거 가능한 언어에 대한 나의 이해는 좋지만 기능이 낮은 오토마타에 대해서는 잘 모릅니다(예:푸시다운 오토마타), 진행 방법을 잘 모르겠습니다.

첫째, 다양한 계산 모델을 학습하는 데 유용한 리소스를 추천해 줄 수 있는 사람이 있나요?저는 문법, 언어, 오토마타, 그리고 이들 모두의 동등성과 차이점을 증명하는 방법에 관심이 있습니다.이상적으로 리소스는 각 모델의 모든 요소를 ​​매우 자세하게 분석하고 비교합니다.

둘째, 시스템을 이러한 계산 모델에 맞추려고 할 때 사용해야 하는 일반적인 접근 방식이나 프레임워크가 있습니까?

Answer 1

나는 컴퓨터 과학에 관한 좋은 교과서를 추천하고 싶습니다. Sipser의 계산 이론 소개, 제 생각에는 매우 좋습니다.다음을 찾을 수도 있습니다. 무료 교과서 같은 내용을 가르치지만 경험이 없어서 추천할 수 없습니다).

다른 접근 방식은 아마도 Wikipedia를 읽는 것일 것입니다.찾고 있는 내용과 순서를 알고 있다면 실제로 Wikipedia 기사에서 많은 정보를 얻을 수 있습니다.또한 불분명한 것이 있으면 일반적으로 Google에서 해당 특정 주제에 대한 더 많은 리소스를 찾을 수 있습니다.

물론, 이것은 ~ 아니다 실제 교과서만큼 훌륭하지만 시작하기 좋은 곳입니다. 지금 바로, 그리고 그것은 무료입니다.

시작점으로 다음 주제에 대해(나열된 순서대로) 읽어 보는 것이 좋습니다.

1. 결정론적 유한 오토마톤
2. 비결정론적 유한 오토마톤, 그리고 DFA와 동일합니다.
3. 일반 언어, 그리고 DFA와 동일합니다.
4. 푸시다운 오토마타
5. 문맥에 구애받지 않는 문법, Pushdown Automata와 동일합니다.
6. 촘스키 계층구조
7. 튜링 기계

이는 사람들이 이야기하는 대부분의 계산 모델에 대해 매우 간략하게 소개할 것입니다. 2:나는 컴퓨터 과학에 관한 좋은 교과서를 추천하고 싶습니다. Sipser의 계산 이론 소개, 제 생각에는 매우 좋습니다).다른 접근 방식은 아마도 Wikipedia를 읽는 것일 것입니다.찾고 있는 내용과 순서를 알고 있다면 실제로 Wikipedia 기사에서 많은 정보를 얻을 수 있습니다.또한 불분명한 것이 있으면 일반적으로 Google에서 해당 특정 주제에 대한 더 많은 리소스를 찾을 수 있습니다.시작점으로 다음 주제에 대해(나열된 순서대로) 읽어 보는 것이 좋습니다.1. 1: http://www.amazon.com/Introduction-Theory-Computation-Second-Michael/dp/0534950973/ref=sr_1_1?ie=UTF8&s=books&qid=1263282346&sr=8-1

Answer 2

다음 링크의 비디오 강의는 계산 이론에 대한 좋은 소개를 제공합니다.이것은 이 주제에 대한 최고의 자료 중 하나입니다.

이 교수의 계산이론 영상강의샤이 사이먼슨

Answer 3

찾기 어려울 수 있는 오래된 텍스트는 Hopcroft와 Ullman의 "오토마타 이론, 언어 및 계산 소개"입니다.여러 가지 에디션이 있습니다. 복잡한 내용을 소개하는 데 최소한의 펀치만 사용하는 만큼 79년이 최고라고 들었습니다.이 책은 비록 작지만 합법적인 교과서이며, 여러분이 찾고 있는 것뿐만 아니라 전체 분야를 소개합니다.나는 다른 출처에서 제외된 "더 까다로운" 증거 중 하나가 귀하의 핵심일 수 있다는 헛된 희망에 대해 이것을 제안합니다.

보다 부드러운 출발점으로 몇 가지 편리한 "벤치마크" 언어가 있습니다.

• 귀하의 모델인 경우 ~할 수 있다 문자열에 동일한 수의 As와 B가 있는 모든 문자열의 언어를 인식하면 적어도 FSM보다 강력합니다.
• 그럴 수 없다면, 그렇지 5월 FSM과 동일합니다.
• 마찬가지로, 귀하의 모델이 ~할 수 있다 문자열에서 동일한 수의 As, B, C가 있는 모든 문자열의 언어를 인식하면 다음과 같습니다. 더 CFG나 PDA보다 강력합니다.

이러한 "벤치마크 언어"는 실제로 변장된 함수일 뿐입니다. 첫 번째는 기본적으로 2개의 단항 숫자가 동일한지 묻는 것이고, 두 번째는 3개의 단항 숫자가 동일한지 묻는 것입니다.그것들은 훌륭하고 단순하며, 특정 모델의 성능보다 높거나 낮은 것으로 잘 알려져 있습니다.나는 더 복잡한 기계에 대한 간단한 것을 알지 못하므로 스스로 할 수도 있습니다.

선형 경계 오토마타인 "LBA" 모델의 경우 TM으로 계산할 수 있는 알려진 자연 언어는 없지만 LBA는 없다고 생각합니다.이 진술은 흐릿한 기억에서 나온 것이므로 공식적인 증거로 받아들이지 마십시오.:)

(마지막으로) "벤치마크" 언어는 평등을 확립하지 않는다는 점에 유의하세요.즉, 모델이 2개의 단항 숫자를 비교할 수 없다면 이는 그렇습니다. ~ 아니다 이는 반드시 FSM과 동일하며 더 약할 수 있음을 의미합니다.언어는 권력보다 더 큰 것과 권력보다 작은 것만을 확립할 것입니다.

완전히 (완전히) 다른 트랙에서 Sipser의 책은 다음을 증명합니다. 등가 정규식과 FSM 사이, PDA와 CFG 사이.어떤 종류의 계산 모델을 고려하고 있는지에 대해 매우 모호하기 때문에 그것이 얼마나 도움이 될지는 잘 모르겠습니다. 그러나 동등성에 대해 확신이 없다면 이것이 좋은 출발점이 될 수 있습니다.