여기에서 언어 L ={WW |W는 {0, 1}}에 속하는 튜링 머신을 만드는 방법을 볼 것입니다. 따라서 이것은 0과 1 두 개의 문자만 사용하는 일종의 언어를 나타냅니다. w는 문자열입니다. 따라서 w =10110이면 튜링 기계는 문자열 z =1011010110을 받아들입니다.
이를 해결하기 위해 이 접근 방식을 사용합니다. 첫 번째는 문자열의 중간점을 찾는 것입니다. 0을 x로, 1을 y로 변환합니다. 계속해서 수행한 후 모든 0과 1이 각각 x와 x로 변환되었을 때 지점에 도달합니다. 이제 우리는 문자열의 중간 지점에 있습니다. 이로써 첫 번째 목표가 완료되었습니다.
이제 중간점의 왼쪽에 있는 모든 x와 y를 0과 1로 변환합니다. 이제 문자열의 전반부는 0과 1의 형태입니다. 문자열의 후반부는 x와 y의 형태입니다.
이제 문자열의 처음부터 다시 시작합니다. 0이 있으면 x로 변환하고 후반부에 도달할 때까지 오른쪽으로 이동합니다. 여기서 x를 찾은 다음 공백(B)으로 변환합니다. 그런 다음 x 또는 x를 찾을 때까지 뒤로 이동합니다. 오른쪽에 있는 0 또는 1을 각각 x 또는 y로 변환하고 이에 따라 문자열의 후반부에 있는 x 또는 y를 공백(B)으로 변환합니다.
문자열의 왼쪽 부분에 있는 모든 기호를 x와 y로 변환하고 문자열의 오른쪽에 있는 모든 기호를 공백으로 변환할 때까지 이 작업을 계속하십시오. 한 부분이 완전히 변환되었지만 나머지 절반의 일부 기호가 변경되지 않은 채로 남아 있으면 문자열이 허용되지 않습니다. 전반부에 해당하는 0 또는 1에 대해 후반부에 x 또는 y를 찾지 못한 경우. 그러면 문자열도 허용되지 않습니다.
상태 전환 다이어그램
