게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

튜링기계 설계과제에서 마커의 사용법에 대해 질문드립니다

 
글 쓰기   답변 달기     게시판 인덱스 -> 046.016 Computational Civilization (Fall 2015)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
이광



가입: 2014년 9월 3일
올린 글: 16

올리기올려짐: 2015년9월16일 14:02    주제: 튜링기계 설계과제에서 마커의 사용법에 대해 질문드립니다 인용과 함께 답변

2번과 3번 과제를 풀기 위해서는 하나 이상의 마커를 사용해야하는데
마커를 테입과 별게로 고려해서 규칙을 짜는 것은 괜찮은데 이를 바닐라 코드로 변환하는 작업이 이해가 잘 안됩니다.
혹시 몇가지 예시를 올려주실 순 없나요?
위로
사용자 정보 보기 비밀 메시지 보내기
로파스
Site Admin


가입: 2012년 9월 9일
올린 글: 280

올리기올려짐: 2015년9월16일 15:05    주제: 인용과 함께 답변

마커를 사용하는 예시를 보여드리면 복사하는 튜링기계에 대한 거의 정확한 답이 되기 때문에 예시를 직접 써드리진 못할 것 같고, 원리를 보다 자세하게 설명해드리겠습니다.

기본적인 튜링머신은 헤더를 통해 테이프의 심볼을 읽고 쓰는 것이 가능합니다. 마커를 추가하게 되면 헤더뿐 아니라 마커에서도 심볼을 읽을 수 있게 되는데, 이를 순수한 튜링머신에 녹이려면, 다음과 같은 기능이 필요합니다.

1. '현재 마커가 어디에 있는지를 표현할 방법'
2. '현재 위치에서 마커가 있는 곳까지 이동할 방법, 다시 원래대로 돌아올 방법'
3. '마커가 있는곳까지 가서 어떠한 심볼을 읽어왔을때, 그 심볼에 맞는 작업을 수행할 수 있는 방법'
4. '마커를 이동시킬 방법'

네가지 모두 쉽게 해결할 수 있습니다.

첫번째는 모든 테이프를 2칸으로 갈라서 한쪽에는 원래 테이프에 있던 심볼을 쓰고, 다른 한쪽에는
마커가 이 칸에 존재하는지 여부를 나타내는 심볼을 쓰면 됩니다.

테이프에 a b b a 이 쓰여있고, 헤더는 두번째 a을, 마커는 첫번째 a을 가르키고 있다면 다음과 같은 테이프로 나타낼 수 있겠죠.

O a X b X b X a (헤더는 두번째a에)

O라는 심볼이 쓰여진 1번째 a를 마커가 가르키고 있는 형태가됩니다.


두번째, 세번째 기능으로, 마커가 있는 곳까지 헤더가 돌아가서 어떤 심볼을 가지고 있는지 읽어오려면, 위 상황에서 헤더를 한칸 왼쪽으로 보내 세모를 빈칸에 쓴 다음, '마커찾는 스테이트'로 넘어가면 됩니다.

O a X b X b 세모 a (헤더는 세모에 있다가 O까지 왼쪽으로)

그다음 O를 만날때까지 왼쪽으로 간 다음에, 한칸 오른쪽으로 가서 어떤 심볼이 있는지를 읽어야 합니다.

O a X b X b 세모 a (헤더는 O에 있다가 기계상태가 'a를 읽었음.'으로 바뀌면서 오른쪽으로 가게 됨)


그다음, 읽은 심볼을 기억할 수 있는 새로운 스테이트로 넘어가서(state이름에 심볼이름을 표현하면 되겠지요) 방금 마커를 찾아올때 표시해뒀던 세모를 찾아 오른쪽으로 가면 됩니다. 세모를 찾았으면 다시 X로 바꿔주고 한칸 오른쪽으로 가서 원래 읽고있던 심볼을 다시 읽어주면 됩니다. 현재 스테이트와 헤더가 읽은 심볼을 참고하여 다음 행동을 하면 될 것입니다.

O a X b X b X a (세모를 찾은 헤더가 세모를 X로 바꾸고 다시 a에 위치하게됨. 이때 기계상태는 아직 'a를 읽었음'. 만약 어떤 규칙표에 헤더가 a를 읽고 마커가 a를 읽었으면 '어떤 행동'을 하라는 규칙이 있다면, 이제부터 그 '어떤 행동'을 하도록 규칙표를 짜면 될 것입니다.)

네번째 기능은 마커를 이동하는 기능은, 위의 과정을 이해했다면 자연스럽게 어떻게 하면 구현될지 알 수 있을 것입니다.(O가 있는 곳까지 이동해서 X로 바꾼 다음 왼쪽이나 오른쪽으로 두칸을 가서 O로 바꿔주면 되겠지요. 그후엔 위에서와 같이 세모를 표시해둔 곳으로 돌아가면 되구요.)

혹시 이해가 안되는 부분이 있다면 또 질문해주세요.

한가지 숙제 팁을 드리자면, 이번 숙제는 마커를 사용해서 구현하고 다시 바닐라 튜링머신으로 녹이는 방법보다, 그냥 처음부터 바닐라튜링머신으로 짜는게 더 편할 수도 있습니다. 마커가 없으면 이번 숙제에 나오는 문제보다 훨씬 복잡한 기계를 구현하기가 너무너무 힘들기 때문에 꼭 필요한 개념이지만, 이번 숙제같은 경우는 마커없이 바로 짜는게 더 쉬울 수도 있습니다.
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 046.016 Computational Civilization (Fall 2015) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay