게시판 인덱스

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

튜링기계 숙제 공지사항 및 팁(중요한 팁 추가!)

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


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

올리기올려짐: 2015년9월17일 14:06    주제: 튜링기계 숙제 공지사항 및 팁(중요한 팁 추가!) 인용과 함께 답변

1. 숙제에 예시로 나온 *과 . 으로 표시된 입력 테잎의 심볼들은 자유롭게 바꾸셔도 되고, 그외에도
원하는대로 마음껏 심볼을 가져다 쓰실 수 있습니다.
가장 편한 방법은 0과 1,2,3,4 와 같은 숫자를 쓰는 것이겠지요.
대신 비교하는 튜링머신의 결과를 출력할때는 문제의 의도에 맞게 0과 1을 사용하도록 해주세요.


2. 저번학기에서 많은 학생들이 실수하신 부분인데, 자연수를 입력으로 받는 튜링기계라면,
'임의의 자연수가 입력으로 들어와도' 의도한 기능이 수행되어야 합니다.
예를들어 숫자 2와 3에 대해서만 비교가 가능한 튜링머신을 제출하시면 안됩니다ㅠ


3. 다른 글에서도 언급했던 팁인데, 이번 숙제는 마커를 사용하여 1차적으로 기계를 제작하고
그것을 바닐라 튜링머신으로 녹이는 방법이 아니라 처음부터 바닐라 튜링머신으로 구현하는 것이
더 쉽게 답을 낼 수 있습니다. 직접 해보신 분은 알겠지만 마커를 사용하는 기계를 바닐라
튜링기계로 구현하려면, 가능하다는 것은 확실하지만 가능하게 하기 위해 해야 할 일의 양이
굉장히 많습니다. 처음부터 바닐라 튜링기계로 구현하시는 게 편할 것입니다.


4. 마커를 사용한 규칙표를 바닐라 튜링기계로 녹여낸 것으로 구현할 계획이라면, 혹은 구현하셨다면 테이프의 모든 칸을 두개로 나눠서 쓰는 것이 필수적일 것입니다. 0110 대신 x0x1x1O0 이런식으로 입력을 받는 것도 정답으로 인정됩니다.


5. 위의 모든것을 줄여서, 테스트페이지에서 돌려보았을때 여러가지 입력에 대해 의도한 작동을 하면 만점입니다. 0110 을 0110110 으로 복사하는 것이나, x0x1x1x0x1x1x0 으로 복사하는 것이나 직관적으로 보면 같은 행동을 하는 것이기 때문에 다 정답입니다. 자잘한 실수들에 대해선 매우 자잘한 감점이 있을 예정입니다.

6. 튜링기계 설계에 완전히 감을 못잡겠다는 질문이 있어 설계의 큰 가이드라인을 하나 제시하고자 합니다. 이것은 제가 생각하기에 이렇게 하면 편할것같다 하는 방식이므로, 이대로 하실 필요는 전혀 없습니다. 참고사항으로 사용해주세요. 복사하는 방법에 대한 것인데, 이것을 잘 응용하면 비교하기도 쉽게 할 수 있을 것입니다.

0110을 복사하려고 할때(헤더는 0에) 한칸 오른쪽으로 헤더를 옮겨 1을 만나고, 이를 복사하기 위해 오른쪽으로 가게 될 것입니다. 빈칸을 만날때까지 오른쪽으로 가서 1을 쓰고 복사를 계속하기 위해 다시 왼쪽으로 갈텐데,(현재상태는 01101 (헤더는 맨 오른쪽 1에)) 이때 첫번째1은 복사를 완료했으므로 두번째1까지만 돌아가야 할 것입니다. 그런데 첫번째까지 복사를 완료했다는 정보를 테잎의 어디에서도 얻을 수 없으므로, 복사를 완료한 1에 대해서는 표시를 하는것이 필요하겠지요. 한가지 예를 들어서 테잎의 상태가 아래 순서와 같이 변하도록 구현하시면 쉽습니다.

0110 -> 0210 -> 02101 -> 02201 -> 022011 -> 0220110

위의 예시에서는 복사가 완료된, 혹은 완료될 1들을 2로 바꾸어놓음으로써 어디까지 복사를 완료했는지 알 수 있게 됩니다. 위의 아이디어를 토대로 살을 붙이면서 규칙표를 작성하시면 쉽게 문제를 해결하실 수 있을 것입니다.

비교하는 기계도 복사하는 기계를 응용하면 쉽게 구현할 수 있는데,
왼쪽에 있는 숫자를 일단 복사해놓고, 두번째 숫자를 비슷한 방식으로 복사해가면서 비교를 할 수 있을 것입니다.
예를들어, 0111010 이 입력으로 들어오면 일단 0111010111을 만들어놓고 두번째 숫자를 복사해보시면 됩니다. 대신 맨 뒤에 1을 다시 쓰도록 복사를 하는게 아니라 첫번째 숫자를 복사해둔 111부분을 하나씩 지우는 방식으로 복사하시면 011101011이 남겠지요. 맨뒤에 11이 남아있으니 첫번째 숫자가 더 크다고 판단할수있고, 그에 대한 결과를 출력하시면 되고, 반대의 경우에도 마찬가지로 알맞은 결과를 출력하면 될 것입니다.



7. 심볼을 바꿔 사용하는 과정에서, *..*을 0110등으로 바꾸시는건 자유롭게 하셔도 되지만, 0112와 같이 바꾸시는건 문제의 의도를 벗어난 것으로 간주하겠습니다. 심볼을 바꾸는 것은 자유지만 같은 *을 앞,뒤라는 의미를 부여해 0과 2로 다르게 바꾸었으므로, 아예 다른 기계를 제작하는 것이 됩니다. 이점 유의해주세요.



추가적인 안내사항이 발생하면 이 글에 추가하도록 하겠습니다.

-이동권 드림.
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 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