คำอธิบายปัญหา
ที่นี่เราจะดูวิธีสร้าง Turing machine สำหรับภาษา L = {AiBjCk | i * j = k; i, j, k ≥ 1} ดังนี้แสดงถึงภาษาประเภทหนึ่งที่เราจะใช้ตัวอักษรแค่สามตัวคือ A, B และ C w คือสตริง เช่นถ้า w = AABBBBCCCCCCCC Turing machine จะยอมรับมัน
เพื่อแก้ปัญหานี้ เราจะใช้วิธีการนี้:
แทนที่ A หนึ่งตัวด้วย x และเคลื่อนที่ขวา จากนั้นข้าม A ทั้งหมดและเคลื่อนที่ขวา
เมื่อหัว (head) ถึง B แรก แทนที่ B หนึ่งตัวด้วย y แล้วเคลื่อนที่ขวาข้าม B ระหว่างทาง และสำหรับ B ที่แทนที่แล้ว ตอนนี้แทนที่ C หนึ่งตัวด้วย z และเคลื่อนที่ซ้าย
ตอนนี้เคลื่อนที่ซ้ายข้าม z และ B ทั้งหมดในทาง
เมื่อ pointer ถึง y ล่าสุด ให้เคลื่อนที่ขวา
ถ้า pointer ชี้อยู่ที่ B ให้ทำซ้ำขั้นตอน 2 ถึง 4 มิฉะนั้นเมื่อ pointer ชี้อยู่ที่ z ให้เคลื่อนที่ซ้ายขณะแทนที่ y ทั้งหมดเป็น B และข้าม A ทั้งหมด
เมื่อ pointer มาถึง x ล่าสุด ให้เคลื่อนที่ขวาหนึ่ง步
ถ้า pointer ยังชี้อยู่ที่ A ให้ทำซ้ำขั้นตอนทั้งหมดข้างต้น มิฉะนั้นเมื่อ head อยู่ที่ y ให้เคลื่อนที่ขวาข้าม y และ z ทั้งหมด
เมื่อถึง $ ให้เคลื่อนที่ซ้าย สตริงจะ被接受
State Transition Diagram
