x^y의 기능 계산기 역할을하는 튜링 머신을 만드는 방법
-
06-07-2019 - |
문제
튜링 머신에 대한 테스트를 공부하고 있으며 다음의 기능 계산기 역할을하는 튜링 머신을 만들어야하는 문제가 있습니다.
f(x,y) = x ^ y
테이프 입력이 다음과 같이 분리 될 것임을 이해합니다.
1's of base 0 1's of exponent
내 테이프 출력이 좋아요
1's of base 0 1's of exponent 0 1's of the computed result
X와 Y를 테이프에 배치하려면 어떻게해야합니까? (멀티 테이프 머신 일 수 있습니다.) 상태 다이어그램은 어떻게 생겼습니까?
참고 : 나는 0과 0을 나타내는 데 사용되는 1을 사용하여 값이 아니라 구분기로 사용하고 있습니다.
그래서:
0 = delimiter
1 = 0
11 = 1
111 = 2
1111= 3
11111= 4
etc.
해결책
나는 여기서 조금 추측하고 있습니다. Turing Machine 시뮬레이터와 함께 연주 한 이래로 시간이 지났습니다. 우선, 작업을 몇 가지 개념적 단계로 나누고 싶습니다.
- 테이프의 다른 숫자 값으로 테이프의 숫자를 증가시킵니다.
- 테이프의 숫자에 테이프의 다른 숫자 값을 곱하십시오 - 이것은 1 단계를 반복적으로 수행하여 수행 할 수 있습니다.
- 테이프에 숫자가 정사각형 - x ^ 2는 테이프에 X를 넣은 다음 자체적으로 곱하여 작업됩니다.
- (마지막 단계) 테이프의 숫자를 테이프의 다른 숫자 값의 힘으로 올려 놓습니다. 2 단계를 반복적으로 수행하여 수행 할 수 있습니다.
작업을 반복적으로 수행하려면 N을 테이프에 넣고 작업을 한 번 수행 한 다음 숫자 N의 끝에서 1을 빼냅니다. 숫자 N이 테이프에서 사라질 때까지 반복하십시오.
바라건대 이것은 어쨌든 당신을 시작하기에 충분합니다. 상태 기계는 이러한 방식으로 기계적으로 다소 기계적으로 구성 될 수 있습니다.
다른 팁
내 자신의 튜링 슈도 코드에서 :
- 입력 A0B를 테이프에 복사합니다
- 테이프에 000010000을 쓰십시오
- 테이프 3의 숫자를 테이프 2에서 곱하십시오.
- a의 시작 부분에서 시작합니다
- 테이프에 0을 쓰기 4
- 복사 번호 3 => 4
- 테이프 3 (3 ++)에서 한 번 앞으로 나아갑니다.
- 끝나지 않는 한 3 단계로 이동합니다
- 테이프 4에서 테이프로 이동 3
- 테이프 2의 숫자 B를 줄입니다
- 테이프 3의 숫자를 테이프 2에서 곱하십시오.
- 테이프 2의 B가 0이 아닌 경우 2 단계로 이동하십시오.
- 테이프 3에서 테이프 1로 답을 복사하십시오
다음은 작동 해야하는 튜링 코드입니다 (테이프는 포인터, 소문자, 입력 테이프가 i
):
# At the start for 2^3
# i: 000111011110000
# ^
_start_ -> *a = 0, start2
start2 [*i==0] -> i++, *a++ = 0, *b++ = 0, start4
start2 [*i==1] -> i++, *a++ = 1, start2
start4 [*i==0] -> *b-- = 0, b--, initc
start4 [*i==1] -> i++, *b++ = 1, start4
initc -> *c++ = 0, *c++ = 1, *c++ = 1, *c-- = 0, mult
# example
# i: 00011101111000
# ^
# a: 001110000
# ^
# b: 001111000
# ^
# c: 00011000
# ^
mult[*b==0]: lastcpy
mult[*b==1]: b--, *d++ = 0, *d++ = 1, rewa
rewa[*a==0]: a++, a++, multcpy
rewa[*a==1]: a--, rewa
multcpy[*c==1]: c++, multcpy2
multcpy[*c==0]: multcpy3
multcpy2[*a==0]: multcpy
multcpy2[*a==1]: *d++ = 1, multcpy2
multcpy3: *d-- = 0, *c = 0, cpydtoc
cpydtoc[*d==1]: d--, *c++ = 1, cpydtoc
cpydtoc[*d==0]: *c-- = 0, mult
lastcpy[*c==1]: *i++ = 1, c--, lastcpy
lastcpy[*c==0]: *i = 0, _finish_
# Should end with
# i: 00011101111011111111100
# ^
오류를 확인하십시오 :)
제휴하지 않습니다 StackOverflow