คำอธิบายปัญหา
ที่นี่เราจะดูวิธีสร้าง Turing machine สำหรับภาษา L = {WW |W belongs to {0, 1}} ดังนี้แสดงถึงภาษาประเภทหนึ่งที่เราจะใช้ตัวอักษรแค่สองตัวคือ 0 และ 1 w คือสตริง เช่นถ้า w = 10110 ดังนั้น Turing machine จะยอมรับสตริง z = 1011010110
เพื่อแก้ปัญหานี้ เราจะใช้วิธีการนี้: สิ่งแรกคือหาจุดกึ่งกลางของสตริง เราจะแปลง 0 เป็น x และ 1 เป็น y หลังจากทำต่อเนื่องๆ จะถึงจุดที่ 0 และ 1 ทั้งหมดถูกแปลงเป็น x และ y ตามลำดับ ตอนนี้เราอยู่ที่กึ่งกลางของสตริง ดังนั้นวัตถุประสงค์แรกเสร็จแล้ว
ตอนนี้ แปลง x และ y ทั้งหมดทางซ้ายของจุดกึ่งกลางกลับเป็น 0 และ 1 ตอนนี้ครึ่งแรกของสตริงอยู่ในรูป 0 และ 1 ครึ่งหลังอยู่ในรูป x และ y
ตอนนี้ เริ่มจากต้นทางของสตริงอีกครั้ง ถ้าคุณมี 0 ให้แปลงเป็น x และเคลื่อนที่ไปขวาจนถึงครึ่งหลัง ที่นี่ถ้าเราพบ x ให้แปลงเป็น blank(B) จากนั้นเคลื่อนที่กลับไปจนกว่าจะพบ x หรือ x เราแปลง 0 หรือ 1 ที่ขวาของมันเป็น x หรือ y ตามลำดับ และในทางกลับกัน แปลง x หรือ y ในครึ่งหลังของสตริงเป็น blank(B)
ทำอย่างนี้ต่อไปจนกว่าจะแปลงสัญลักษณ์ทั้งหมดทางซ้ายของสตริงเป็น x และ y และสัญลักษณ์ทั้งหมดทางขวาของสตริงเป็น blanks เมื่อส่วนหนึ่งแปลงเสร็จสมบูรณ์แต่ยังมีสัญลักษณ์ในอีกครึ่งเหลืออยู่ที่ไม่ได้แปลง สตริงจะไม่被接受 ถ้าเราไม่พบ x หรือ y ในครึ่งหลังสำหรับ 0 หรือ 1 ที่ตรงกันในครึ่งแรก สตริงก็จะไม่被接受
State Transition Diagram
