나는 언어에 관한 책을 읽고있다. & 오토 마트와 나는 튜링 기계를 이해하지 못한다. 나는 DFA의 NFA와 Pushdown Automata에 대해 아무런 문제없이 가르쳤다. 누군가이 일을 설명해 주시겠습니까?튜링 기계
B = | 입력 011,000에서 시작될 때 단계 2 3을 계산하는 동안 {승 # 승 ∈ {0 승, 1} *}
다음 그림은 ML의 테이프 여러 스냅 샷을 포함 # 011000.
감사 alot을!
튜링 기계는 기호가 저장된 테이프가있는 가정용 기계입니다. 테이프에서 기호를 읽거나 테이프에 기호를 쓸 수있는 여러 헤드를 가질 수 있습니다.
문법에 따라 "w # w"형식의 문자열 인 B = {w # w | w ∈ {0, 1} *}이 있습니다. 여기서 w는 0과 1의 조합이거나 none입니다. 모든. 그러면이 특별한 예제에서 w = 011000이라고 가정 해 봅시다. 결과 문자열은 011000 # 011000이고 튜링 기계는이 문법을 따르는 지 확인합니다.
튜링 기계에는이 경우 헤드가 하나 있습니다. 그것은 문자열의 시작 부분에서 시작됩니다. 0 인 첫 번째 문자를 읽습니다. "x"라고 표시합니다. 그런 다음 # 바로 뒤에 가서 방금 읽은 내용이 일치하는지 확인합니다. 이 경우에도 0이므로 'x'와 일치하는 것으로 표시됩니다. 그런 다음 이전 위치로 돌아가 다음 문자에 대해 동일한 작업을 수행합니다. #에 도달 할 때까지이 작업을 계속합니다. 해시 또는 #을 읽으면 문자열의 끝을 확인하고 문자열의 끝인 경우이 문자열을 받아 들여 주어진 문법을 따르게됩니다.
#을 지나친 후, 기호는 모두 x이어야합니다. 기계가 x 옆에 다른 기호를 읽으면 문자열이 문법에 허용되지 않음을 의미합니다. – Keale
"끝없는 열의 호텔 객실을 상상해보십시오. 각 방에는 전구와 스위치가있어 처음에는 모든 방이 어두워요. 로봇은 방 중 하나에서 시작하여 스위치를 조작 할 수 있습니다 인접한 방으로 이동
로봇에는 여러 가지 상태가 있으며 각 상태는 현재 공간이 밝은 지 또는 어두운 지에 따라 수행해야 할 작업을 결정합니다. 예를 들어 로봇의 규칙에는 이러한 상태가 포함될 수 있습니다 :
는은 "무서워"상태 : 실내가 어두운
경우, 빛과 움직임을 켜 왼쪽 방으로.
실내가 밝은 경우는 아무 것도하지 말고 "정상"상태로 이동하십시오. "정상"상태 :
실내가 밝은 경우 조명을 끄고 오른쪽에있는 방으로 이동하십시오.
그렇지 않으면 "겁나는"상태로 이동하십시오.
하나의 특별한 상태는 "중지"상태입니다. 로봇이이 상태에서 자신을 발견하면 프로세스가 완료됩니다.
로봇에 n 개의 상태 ("정지"상태가 포함되지 않음)가 있다고 가정하고 정지합니다. 이 시점에서 라이트 룸의 최대 수는 얼마입니까?
이 시스템은 튜링 기계에 직접 우의를 품고 있습니다. 호텔은 테이프이고 로봇은 튜링 기계이며 어두운 방과 밝은 방은 0과 1 셀입니다."
그것은 googology 위키에서입니다. 나는 물론,이 텍스트 나 이후 개선되었습니다, 여기에 아이디어를 주었지만.
는 ** 튜링 기계 학습,하지만 당신은 알고 계십니까 질문이 불완전 좋아입니다
** 각 머리 위치에 국가가 무엇인지 알지 못함 !!! 튜링 기계가 동일한 상태로 유지되고 유한 정보에 대한 상태가 바뀌면 올바른 것일 수 있습니다. 내 의견은 혼란스러워 보입니다. 하지만 상태에 대한 정보를 추가해야 할 필요가 있습니다. 그러면 매우 쉬울 것입니다 ... –
새로운 기능이 새로 추가되었습니다. 선삭기는 DFA의 NFA 및 푸시 다운 자동 매스터보다 ** ** 간단합니다 ** 기호 표기법에 문제가 발생할 수 있습니다. 일단 당신이 거기에 집중 해 :) 행운을 빌어 요 .. –