อ่าน 7 นาที
เครื่องจักรหลังทัวริง
เครื่องโพสต์หรือเครื่องโพสต์-ทัวริงเป็น "การกำหนดโปรแกรม" ของเครื่องทัวริง ประเภทหนึ่ง ซึ่งประกอบด้วยรูปแบบหนึ่งของแบบ จำลอง การคำนวณที่เทียบเท่าทัวริงของเอมิล...
เครื่องจักรหลังทัวริง
เครื่องโพสต์หรือเครื่องโพสต์-ทัวริง[ 1 ]เป็น "การกำหนดโปรแกรม" ของเครื่องทัวริง ประเภทหนึ่ง ซึ่งประกอบด้วยรูปแบบหนึ่งของแบบ จำลอง การคำนวณที่เทียบเท่าทัวริงของเอมิล โพสต์แบบจำลองของโพสต์และแบบจำลองของทัวริง แม้จะคล้ายคลึงกันมาก แต่ก็ได้รับการพัฒนาอย่างอิสระ บทความของทัวริงได้รับการส่งให้ตีพิมพ์ในเดือนพฤษภาคม พ.ศ. 2479 ตามด้วยบทความของโพสต์ในเดือนตุลาคม เครื่องโพสต์-ทัวริงใช้อักษรไบนารีลำดับอนันต์ของ ตำแหน่ง จัดเก็บ ไบนารี และภาษาการเขียนโปรแกรม แบบดั้งเดิม ที่มีคำสั่งสำหรับการเคลื่อนที่แบบสองทิศทางระหว่างตำแหน่งจัดเก็บและการเปลี่ยนแปลงเนื้อหาทีละตำแหน่ง ชื่อ "โปรแกรมโพสต์-ทัวริง" และ "เครื่องโพสต์-ทัวริง" ถูกใช้โดยมาร์ติน เดวิสในปี พ.ศ. 2516-2517 (เดวิส พ.ศ. 2516 หน้า 69 เป็นต้นไป) ต่อมาในปี พ.ศ. 2523 เดวิสใช้ชื่อ "โปรแกรมทัวริง-โพสต์" (เดวิส ใน สตีน หน้า 241)
1936: แบบจำลองหลังการผลิต
ในบทความเรื่อง "กระบวนการเชิงผสมจำกัด—สูตรที่ 1" ที่ตีพิมพ์ในปี 1936 เอมิล โพสต์ได้อธิบายแบบจำลองที่เขาตั้งข้อสันนิษฐานว่า " มีความเทียบเท่าเชิงตรรกะกับความเป็นเหตุเป็นผลแบบเวียนเกิด "
แบบจำลองการคำนวณของโพสต์แตกต่างจากแบบจำลองเครื่องจักรทัวริงตรงที่มีการ "แยกย่อย" การกระทำที่ "คอมพิวเตอร์" มนุษย์จะดำเนินการในระหว่างการคำนวณมากขึ้น[ 2 ]
แบบจำลองของโพสต์ใช้ " พื้นที่ สัญลักษณ์ " ซึ่งประกอบด้วย "ลำดับอนันต์สองทางของพื้นที่หรือกล่อง" โดยแต่ละกล่องสามารถอยู่ในสถานะใดสถานะหนึ่งจากสองสถานะที่เป็นไปได้ คือ "ถูกทำเครื่องหมาย" (เช่น ด้วยเส้นแนวตั้งเส้นเดียว) และ "ไม่ถูกทำเครื่องหมาย" (ว่างเปล่า) ในตอนเริ่มต้น กล่อง จำนวนจำกัดจะถูกทำเครื่องหมาย ส่วนที่เหลือจะถูกทำเครื่องหมาย "คนงาน" จะเคลื่อนที่ไปมาระหว่างกล่อง โดยอยู่ในและทำงานในกล่องเพียงกล่องเดียวในแต่ละครั้ง ตาม "ชุดคำสั่ง" ( คำแนะนำ ) ที่กำหนดไว้จำนวนจำกัด ซึ่งมีหมายเลขกำกับตามลำดับ (1, 2, 3, ..., n ) โดยเริ่มจากกล่องที่ "เลือกไว้เป็นจุดเริ่มต้น" คนงานจะต้องปฏิบัติตามชุดคำแนะนำทีละข้อ เริ่มจากคำแนะนำที่ 1
มีขั้นตอนการทำงานพื้นฐานที่แตกต่างกันห้าอย่างที่คนงานสามารถดำเนินการได้:
- (ก) ทำเครื่องหมายที่กล่องที่บรรจุสิ่งของนั้น หากกล่องนั้นว่างเปล่า
- (ข) ลบเครื่องหมายในช่องที่ทำเครื่องหมายไว้ หากมีการทำเครื่องหมายไว้
- (ค) ย้ายไปยังกล่องทางด้านขวา
- (d) ย้ายไปยังกล่องทางด้านซ้าย
- (e) การพิจารณาว่ากล่องที่บรรจุสิ่งของนั้นมีการทำเครื่องหมายไว้หรือไม่
จากนั้น " คำ สั่ง" (คำแนะนำ) ที่ i ที่มอบให้แก่คนงานจะต้องอยู่ในรูปแบบใดรูปแบบหนึ่งต่อไปนี้:
- ดำเนินการO i [ O i = (a), (b), (c) หรือ (d)] แล้วจึงปฏิบัติตามคำแนะนำ j i
- ดำเนินการตามขั้นตอน (e) และตามคำตอบว่าเป็นใช่หรือไม่ใช่ ให้ปฏิบัติตามคำแนะนำ j i ′หรือ j i ″ ตามลำดับ
- หยุด .
(ข้อความที่เว้นวรรคและตัวเอียงด้านบนเป็นไปตามต้นฉบับ) โพสต์กล่าวว่าสูตรนี้อยู่ใน "ขั้นตอนเริ่มต้น" ของการพัฒนา และกล่าวถึงความเป็นไปได้หลายประการสำหรับ "ความยืดหยุ่นที่มากขึ้น" ใน "รูปแบบสุดท้าย" ซึ่งรวมถึง
- แทนที่กล่องจำนวนอนันต์ด้วยพื้นที่สัญลักษณ์ที่ขยายได้แบบจำกัด "ขยายการดำเนินการพื้นฐานเพื่อให้สามารถขยายพื้นที่สัญลักษณ์แบบจำกัดที่กำหนดไว้ได้ตามความจำเป็นในระหว่างกระบวนการ"
- การใช้ตัวอักษรที่มีสัญลักษณ์มากกว่าสองตัว หรือ "การมีมากกว่าหนึ่งวิธีในการทำเครื่องหมายในช่อง"
- โดยการนำ "วัตถุทางกายภาพจำนวนจำกัดมาใช้เป็นตัวชี้ ซึ่งคนงานสามารถระบุและเคลื่อนย้ายจากกล่องหนึ่งไปยังอีกกล่องหนึ่งได้"
ปี 1947: โพสต์ทำการลดรูปทูเพิล 5 ตัวของทัวริงให้เหลือทูเพิล 4 ตัวอย่างเป็นทางการ
ดังที่ได้กล่าวไว้โดยย่อในบทความเรื่องเครื่องจักรทัวริงโพสต์ ในบทความของเขาเมื่อปี 1947 ( ความไม่สามารถแก้ปัญหาแบบเรียกซ้ำของปัญหาของธู ) ได้แยกย่อยทูเพิล 5 ตัวของทัวริงออกเป็นทูเพิล 4 ตัว:
- "ชุดคำสั่งสี่ชุดของเรากลายเป็นชุดคำสั่งห้าชุดในการพัฒนาของทัวริง กล่าวคือ ในขณะที่คำสั่งมาตรฐานของเราสั่งให้พิมพ์ (พิมพ์ทับ) หรือเคลื่อนที่ ซ้ายหรือขวา คำสั่งมาตรฐานของทัวริงจะสั่งให้พิมพ์และเคลื่อนที่ ขวา ซ้าย หรือไม่เคลื่อนที่เลยเสมอ" (เชิงอรรถที่ 12, ไม่สามารถตัดสินได้ , หน้า 300)
เช่นเดียวกับทัวริง เขาได้นิยามการลบว่าเป็นการพิมพ์สัญลักษณ์ "S0" ดังนั้นแบบจำลองของเขาจึงยอมรับควอดรูเพิลได้เพียงสามประเภทเท่านั้น (ดูUndecidableหน้า 294)
- q i S j L q l ,
- q i S j R q l ,
- q i S j S k q l
ในเวลานั้น เขายังคงยึดถือแบบแผนเครื่องจักรสถานะของทัวริงอยู่ กล่าวคือ เขายังไม่ได้กำหนดแนวคิดของ การดำเนินการ ตามลำดับที่สมมติขึ้นจนกว่าการทดสอบสัญลักษณ์เฉพาะจะ "แยก" การดำเนินการไปยังที่อื่นอย่างเป็นทางการ
ปี 1954, 1957: นางแบบหวัง
Wang (ปี 1957 แต่ได้นำเสนอต่อ ACM ในปี 1954) มักถูกอ้างถึง (ดู Minsky (1967), หน้า 200) ว่าเป็นแหล่งที่มาของ "การกำหนดรูปแบบโปรแกรม" ของเครื่องทัวริงแบบเทปไบนารีโดยใช้คำสั่งหมายเลขจากชุด
- เขียน 0
- เขียน 1
- เลื่อนไปทางซ้าย
- เลื่อนไปทางขวา
- ถ้าสแกน 0 ให้ไปที่คำแนะนำi
- ถ้ากำลังสแกน 1 ให้ไปที่คำแนะนำj
เครื่องจักรทัวริงแบบเทปไบนารีใดๆ ก็สามารถแปลงเป็น "โปรแกรมหวัง" ที่เทียบเท่ากันได้โดยง่ายโดยใช้คำสั่งข้างต้น
ปี 1974: เปิดตัวโมเดล Davis รุ่นแรก
มาร์ติน เดวิส เป็น นักศึกษา ปริญญาตรีของเอมิล โพสต์ และสำเร็จการศึกษาระดับปริญญาเอก ร่วมกับ สตีเฟน คลีน ภายใต้การดูแล ของอลอนโซ เชิร์ช (เดวิส (2000) เชิงอรรถที่ 1 และ 2 หน้า 188)
แบบจำลองต่อไปนี้ที่เขานำเสนอในการบรรยายชุดหนึ่งให้กับสถาบัน Courant ที่ NYU ในปี 1973–1974 นี่คือแบบจำลองที่เดวิสใช้ชื่อ "เครื่องจักรหลังทัวริง" อย่างเป็นทางการพร้อมกับ "ภาษาหลังทัวริง" [ 2 ]คำสั่งต่างๆ ถือว่าดำเนินการตามลำดับ (เดวิส 1974, หน้า 71):
ปี 1978: รุ่นเดวิสที่สอง
แบบจำลองต่อไปนี้ปรากฏในบทความเรื่อง " การคำนวณคืออะไร?"ในหนังสือของสตีน หน้า 241–267 ด้วยเหตุผลบางประการ เดวิสได้เปลี่ยนชื่อแบบจำลองของเขาเป็น "เครื่องจักรทัวริง-โพสต์" (โดยมีข้อผิดพลาดเกิดขึ้นในหน้า 256)
ในแบบจำลองต่อไปนี้ เดวิสกำหนดหมายเลข "1" ให้กับ "เครื่องหมาย/ขีดทับ" ของโพสต์ และ "0" ให้กับช่องว่างเปล่า เดวิสกล่าวว่า: "ตอนนี้เราพร้อมที่จะแนะนำภาษาการเขียนโปรแกรมทัวริง-โพสต์แล้ว ในภาษานี้มีคำสั่งเจ็ดประเภท:
- "พิมพ์ครั้งที่ 1
- "พิมพ์ 0
- "ไปทางขวา"
- "ไปทางซ้าย"
- "ไปที่ขั้นตอนที่ 1 ถ้าสแกนหมายเลข1 แล้ว"
- "ไปที่ขั้นตอนที่ i หากสแกนได้0"
- "หยุด
"โปรแกรม Turing–Post จึงเป็นรายการคำสั่ง ซึ่งแต่ละคำสั่งเป็นหนึ่งในเจ็ดประเภทนี้ แน่นอนว่าในโปรแกรมจริง ตัวอักษรiในขั้นตอนประเภทที่ห้าหรือหกจะต้องถูกแทนที่ด้วยจำนวนเต็มบวกที่แน่นอน" (Davis ใน Steen, หน้า 247)
1994 (พิมพ์ครั้งที่ 2): โมเดลโปรแกรม Post-Turing ของ Davis–Sigal–Weyuker
"แม้ว่าสูตรของทิวริงที่เรานำเสนอจะใกล้เคียงกับสูตรดั้งเดิมที่เอมิล โพสต์เสนอไว้ แต่การวิเคราะห์การคำนวณของทิวริงต่างหากที่ทำให้สูตรนี้ดูเหมาะสมอย่างยิ่ง ภาษาดังกล่าวมีบทบาทพื้นฐานในวิทยาศาสตร์คอมพิวเตอร์ เชิงทฤษฎี " (เดวิสและคณะ (1994) หน้า 129)
แบบจำลองนี้อนุญาตให้พิมพ์สัญลักษณ์ได้หลายตัว แบบจำลองนี้อนุญาตให้ใช้ B (ว่างเปล่า) แทน S0 เทปมีความยาวไม่จำกัดในทั้งสองทิศทาง หัวอ่านหรือเทปจะเคลื่อนที่ แต่คำจำกัดความของขวาและซ้ายจะระบุผลลัพธ์เดียวกันเสมอในทั้งสองกรณี (ทิวริงใช้แบบแผนเดียวกันนี้)
- พิมพ์ σ ;แทนที่สัญลักษณ์ที่สแกนด้วย σ
- ถ้า σ ไปที่ L ; ถ้าสัญลักษณ์ที่สแกนได้คือ σ แล้ว ให้ไปที่คำสั่ง "แรก" ที่มีป้ายกำกับ L
- ขวา ; สแกนช่องสี่เหลี่ยมที่อยู่ทางขวาของช่องสี่เหลี่ยมที่กำลังสแกนอยู่ทันที
- ซ้าย ; สแกนช่องสี่เหลี่ยมที่อยู่ทางซ้ายของช่องสี่เหลี่ยมที่กำลังสแกนอยู่
โมเดลนี้ลดรูปเหลือเป็นเวอร์ชันไบนารี { 0, 1 } ที่แสดงไว้ข้างต้น ดังที่แสดงไว้ที่นี่:
- พิมพ์ 0 = ลบ ;แทนที่สัญลักษณ์ที่สแกนด้วย 0 = B = ว่างเปล่า
- พิมพ์ 1 ;แทนที่สัญลักษณ์ที่สแกนด้วย 1
- ถ้าสัญลักษณ์ที่สแกนได้เป็น 0 ให้ไปที่คำสั่งแรกที่มีป้ายกำกับว่า L
- ถ้าสัญลักษณ์ที่สแกนได้คือ 1 ให้ไปที่คำสั่งแรกที่มีป้ายกำกับว่า L
- ขวา ; สแกนช่องสี่เหลี่ยมที่อยู่ทางขวาของช่องสี่เหลี่ยมที่กำลังสแกนอยู่ทันที
- ซ้าย ; สแกนช่องสี่เหลี่ยมที่อยู่ทางซ้ายของช่องสี่เหลี่ยมที่กำลังสแกนอยู่
ตัวอย่างของเครื่องจักรหลังทัวริง
การแยกกลุ่มควินทูเพิลของทัวริงออกเป็นลำดับของคำสั่งโพสต์ทัวริง
วิธีการ "ลดทอน" (การแยกส่วน การทำให้เป็นอะตอม) ต่อไปนี้ – จากทูเพิล 5 สัญลักษณ์ของทัวริงไปเป็นลำดับของคำสั่งโพสต์ทัวริง 2 สัญลักษณ์ – สามารถพบได้ใน Minsky (1961) เขากล่าวว่าการลดทอนนี้ไปเป็น " โปรแกรม ... ลำดับของคำสั่ง " เป็นไปตามแนวคิดของเครื่อง B ของ Hao Wang (ตัวเอียงในต้นฉบับ ดู Minsky (1961) หน้า 439)
(การลดรูปของมินสกีให้เหลือสิ่งที่เขาเรียกว่า "รูทีนย่อย" ส่งผลให้มีคำสั่งหลังทัวริง 5 คำสั่ง แทนที่จะเป็น 7 คำสั่ง เขาไม่ได้แยกคำสั่ง Wi0: "เขียนสัญลักษณ์ Si0; ไปยังสถานะใหม่ Mi0" และ Wi1: "เขียนสัญลักษณ์ Si1; ไปยังสถานะใหม่ Mi1" ออกเป็นคำสั่งย่อย วิธีการต่อไปนี้จะแยกคำสั่ง Wi0 และ Wi1 ออกเป็นคำสั่งย่อยเพิ่มเติม ในส่วนอื่นๆ วิธีการทั้งสองเหมือนกันทุกประการ)
การลดรูปทัวริง 5-tuple ให้เป็นคำสั่งหลังทัวริงนี้ อาจไม่ได้ทำให้ได้โปรแกรมหลังทัวริงที่มีประสิทธิภาพ แต่จะยังคงรักษาความถูกต้องตามโปรแกรมทัวริงดั้งเดิมไว้
ในตัวอย่างต่อไปนี้ Turing 5-tuple แต่ละตัวของ busy beaver 2 สถานะจะแปลงเป็น
- การ "กระโดด" แบบมีเงื่อนไขเบื้องต้น (goto, branch) ตามด้วย
- คำสั่งการทำงานของเทป 2 คำสั่งสำหรับกรณี "0" – พิมพ์หรือลบหรือไม่มี ตามด้วยซ้ายหรือขวาหรือไม่มี ตามด้วย
- เป็นการ "กระโดด" แบบไม่มีเงื่อนไขสำหรับกรณี "0" ไปยังคำสั่งถัดไป
- คำแนะนำการทำงานของเทป 2 แบบสำหรับเคส "1" – พิมพ์หรือลบหรือไม่มี ตามด้วยซ้ายหรือขวาหรือไม่มี ตามด้วย
- เป็นการ "กระโดด" แบบไม่มีเงื่อนไขสำหรับกรณี "1" ไปยังคำสั่งถัดไป
รวมแล้ว มีคำสั่งทั้งหมด 1 + 2 + 1 + 2 + 1 = 7คำสั่งต่อสถานะทัวริงหนึ่งสถานะ
ตัวอย่างเช่น สถานะทัวริง "A" ของ Busy Beaver ที่มี 2 สถานะ ซึ่งเขียนเป็นทูเพิล 5 ตัว 2 บรรทัด มีดังนี้:
| การกำหนดค่า m เริ่มต้น (สถานะทัวริง) | สัญลักษณ์เทป | การดำเนินการพิมพ์ | การเคลื่อนไหวของเทป | การกำหนดค่า m ขั้นสุดท้าย (สถานะทัวริง) |
|---|---|---|---|---|
| เอ | 0 | พี | อาร์ | บี |
| เอ | 1 | พี | แอล | บี |
ตารางนี้แสดงถึง "คำสั่ง" ของทัวริงเพียงคำสั่งเดียว แต่เราจะเห็นว่ามันประกอบด้วยสองบรรทัดของทูเพิล 5 ตัว บรรทัดหนึ่งสำหรับกรณี "สัญลักษณ์เทปใต้หัวอ่าน = 1" และอีกบรรทัดสำหรับกรณี "สัญลักษณ์เทปใต้หัวอ่าน = 0" ทัวริงสังเกต ( Undecidable , หน้า 119) ว่าสองคอลัมน์ซ้ายสุด – "การกำหนดค่า m" และ "สัญลักษณ์" – แสดงถึง "การกำหนดค่า" ปัจจุบันของเครื่อง – สถานะของเครื่องรวมทั้งเทปและตาราง ณ ขณะนั้น – และสามคอลัมน์สุดท้ายคือ "พฤติกรรม" ต่อไปของเครื่อง เนื่องจากเครื่องไม่สามารถอยู่ในสอง "สถานะ" พร้อมกันได้ เครื่องจึงต้อง "แยก" ไปยังการกำหนดค่าใดการกำหนดค่าหนึ่ง:
| การกำหนดค่า m เริ่มต้นและสัญลักษณ์ S | การดำเนินการพิมพ์ | การเคลื่อนไหวของเทป | การกำหนดค่า m ขั้นสุดท้าย |
|---|---|---|---|
| S=0 → | พี → | อาร์ → | บี |
| → อะ < | |||
| S=1 → | พี → | ล → | บี |
หลังจาก "การแยกสาขาการกำหนดค่า" (J1 xxx) หรือ (J0 xxx) เครื่องจะทำตาม "พฤติกรรม" หนึ่งในสองอย่างต่อไปนี้ เราจะแสดงรายการพฤติกรรมทั้งสองนี้ไว้ในบรรทัดเดียวกัน และกำหนดหมายเลข (หรือป้ายกำกับ) ตามลำดับ (ไม่ซ้ำกัน) ใต้การกระโดดแต่ละครั้ง (การแยกสาขา การไปยัง) เราจะใส่ "หมายเลข" (ที่อยู่ ตำแหน่ง) ของการกระโดดนั้น:
| การกำหนดค่า m เริ่มต้นและสัญลักษณ์ S | การดำเนินการพิมพ์ | การเคลื่อนไหวของเทป | กรณีการกำหนดค่า m สุดท้าย S=0 | การดำเนินการพิมพ์ | การเคลื่อนไหวของเทป | กรณีการกำหนดค่า m สุดท้าย S=1 | |
|---|---|---|---|---|---|---|---|
| ถ้า S=0 แล้ว: | พี | อาร์ | บี | ||||
| → อะ < | |||||||
| ถ้า S=1 แล้ว: | พี | แอล | บี | ||||
| คำแนะนำ # | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| การเรียนการสอนหลังทัวริง | เจ1 | พี | อาร์ | เจ | พี | แอล | เจ |
| ข้ามไปยังคำแนะนำ # | 5 | บี | บี |
ตามหลักการของเครื่องจักรหลังทัวริง คำสั่งพิมพ์ ลบ ซ้าย และขวา แต่ละคำสั่งประกอบด้วยการกระทำสองอย่าง:
- การทำงานของเทป: {P, E, L, R} จากนั้น
- การดำเนินการกับตาราง: ไปยังคำสั่งถัดไปตามลำดับ
และตามหลักการของเครื่องจักรหลังทัวริง การ "กระโดด" แบบมีเงื่อนไข J0xxx, J1xxx ประกอบด้วยการกระทำสองอย่าง:
- การทำงานของเทป: ดูสัญลักษณ์บนเทปใต้หัวอ่าน
- การทำงานของตาราง: ถ้าสัญลักษณ์เป็น 0 (1) และ J0 (J1) ให้ไปที่ xxx มิฉะนั้นให้ไปที่คำสั่งถัดไปตามลำดับ
และตามหลักการของเครื่องจักรหลังทัวริง การ "กระโดด" แบบไม่มีเงื่อนไข Jxxx ประกอบด้วยการกระทำเพียงครั้งเดียว หรือหากเราต้องการทำให้ลำดับการกระทำ 2 ครั้งเป็นแบบปกติ:
- การทำงานของเทป: ดูสัญลักษณ์บนเทปใต้หัวอ่าน
- การดำเนินการของตาราง: ถ้าสัญลักษณ์เป็น 0 ให้ไปที่ xxx มิฉะนั้นถ้าสัญลักษณ์เป็น 1 ให้ไปที่ xxx
จำเป็นต้องใช้การกระโดดแบบใดบ้าง และจำนวนเท่าใด? การกระโดดแบบไม่มีเงื่อนไขJ xxx คือJ0ตามด้วยJ1 ทันที (หรือในทางกลับกัน) หวัง (1957) ยังแสดงให้เห็นว่าจำเป็นต้องใช้การกระโดดแบบมีเงื่อนไขเพียงครั้งเดียวเท่านั้น นั่นคือJ0 xxx หรือJ1 xxx อย่างไรก็ตาม ด้วยข้อจำกัดนี้ การเขียนคำสั่งสำหรับเครื่องจักรจึงทำได้ยาก มักจะใช้เพียงสองครั้งเท่านั้น เช่น
- { J0 xxx, J1 xxx }
- { J1 xxx, J xxx }
- { J0 xxx, J xxx },
แต่การใช้ { J0 xxx, J1 xxx, J xxx } ทั้งสามตัวจะช่วยลดคำสั่งเพิ่มเติมลงได้ ในตัวอย่าง Busy Beaver แบบ 2 สถานะ เราใช้เพียง { J1 xxx, J xxx } เท่านั้น
บีเวอร์ขยัน 2 รัฐ
ภารกิจของบีเวอร์จอมซนคือการพิมพ์เลข 1 ให้ได้มากที่สุดก่อนที่จะหยุด คำสั่ง "พิมพ์" จะเขียนเลข 1 คำสั่ง "ลบ" (ไม่ได้ใช้ในตัวอย่างนี้) จะเขียนเลข 0 (นั่นคือเหมือนกับ P0) เทปจะเคลื่อนที่ไปทาง "ซ้าย" หรือ "ขวา" (นั่นคือ "หัวอ่าน" อยู่กับที่)
ตารางสถานะสำหรับ Busy Beaverเครื่องจักรทัวริง 2 สถานะ:
| สัญลักษณ์เทป | สถานะปัจจุบันA | สถานะปัจจุบันB | ||||
|---|---|---|---|---|---|---|
| เขียนสัญลักษณ์ | ย้ายเทป | รัฐถัดไป | เขียนสัญลักษณ์ | ย้ายเทป | รัฐถัดไป | |
| 0 | 1 | อาร์ | บี | 1 | แอล | เอ |
| 1 | 1 | แอล | บี | 1 | เอ็น | ชม |
คำแนะนำสำหรับเวอร์ชันหลังทัวริงของ Busy Beaver แบบ 2 สถานะ: โปรดสังเกตว่าคำสั่งทั้งหมดอยู่บนบรรทัดเดียวกันและเรียงลำดับกัน นี่เป็นการเปลี่ยนแปลงที่สำคัญจากเวอร์ชัน "ทัวริง" และอยู่ในรูปแบบเดียวกับสิ่งที่เรียกว่า " โปรแกรมคอมพิวเตอร์ "
| คำแนะนำ # | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| คำแนะนำ | เจ1 | พี | อาร์ | เจ | พี | แอล | เจ | เจ1 | พี | แอล | เจ | พี | เอ็น | เจ | ชม |
| ข้ามไปที่ # | 5 | 8 | 8 | 12 | 1 | 15 | |||||||||
| ป้ายกำกับสถานะทัวริง | เอ | บี | ชม |
อีกทางเลือกหนึ่ง เราอาจเขียนตารางเป็นสตริงก็ได้ การใช้ "ตัวคั่นพารามิเตอร์" ":" และตัวคั่นคำสั่ง "," เป็นสิ่งที่เราเลือกเองทั้งหมดและไม่ได้ปรากฏอยู่ในแบบจำลอง ไม่มีข้อกำหนดตายตัว (แต่ดู Booth (1967) หน้า 374 และ Boolos และ Jeffrey (1974, 1999) หน้า 23) สำหรับแนวคิดที่เป็นประโยชน์บางอย่างเกี่ยวกับวิธีการรวม ข้อกำหนด ของแผนภาพสถานะเข้ากับคำสั่ง – เช่น การใช้ลูกศรเพื่อระบุปลายทางของการกระโดด) ในตัวอย่างด้านล่าง คำสั่งจะเรียงลำดับโดยเริ่มจาก "1" และพารามิเตอร์/"ตัวถูกดำเนินการ" ถือเป็นส่วนหนึ่งของคำสั่ง/"รหัสการทำงาน" ของพวกมัน:
- J1:5, P, R, J:8, P, L, J:8, J1:12, P, L, J1:1, P, N, J:15, H
หมายเหตุ
- ^ Rajendra Kumar, Theory of Automata , Tata McGraw-Hill Education, 2010, หน้า 343.
- ในบทที่ XIII เรื่องฟังก์ชันที่คำนวณได้ Kleene ได้นำแบบจำลอง ของ Post มาใช้ โดยแบบจำลองของ Kleene ใช้ช่องว่างและสัญลักษณ์ "เครื่องหมายนับ ¤" หนึ่งตัว (Kleene หน้า 358) ซึ่งเป็น "วิธีการที่ใกล้เคียงกับ Post 1936 ในบางแง่มุม Post 1936 พิจารณาการคำนวณด้วยเทปอนันต์สองทางและสัญลักษณ์เพียงตัวเดียว" (Kleene หน้า 361) Kleene สังเกตว่าวิธีการของ Post ช่วยลด "การกระทำของ Turing" (Kleene หน้า 379) ลงไปเป็น "การกระทำอะตอมิก" (Kleene หน้า 357) ได้อีกด้วย ตามที่ Kleene อธิบายไว้ "การกระทำของ Turing" คือการกระทำ 3 อย่าง (ตามลำดับเวลา) ที่ระบุไว้ในบรรทัดของตาราง Turing: (i) พิมพ์สัญลักษณ์/ลบ/ไม่ทำอะไรเลย ตามด้วย (ii) เลื่อนเทปไปทางซ้าย/เลื่อนเทปไปทางขวา/ไม่ทำอะไรเลย ตามด้วย (iii) ทดสอบเทป-ไปยังคำสั่งถัดไป: เช่น "s1Rq1" หมายถึง "พิมพ์สัญลักษณ์ "¤" จากนั้นเลื่อนเทปไปทางขวา จากนั้นถ้าสัญลักษณ์บนเทปเป็น "¤" ให้ไปยังสถานะ q1" (ดูตัวอย่างของ Kleene หน้า 358) Kleene สังเกตว่า Post ได้แยกการกระทำ 3 อย่างนี้ออกเป็นสองประเภทของการกระทำ 2 อย่าง ประเภทแรกคือการกระทำ "พิมพ์/ลบ" ประเภทที่สองคือการกระทำ "เลื่อนเทปซ้าย/ขวา": (1.i) พิมพ์สัญลักษณ์/ลบ/ไม่ทำอะไรเลย ตามด้วย (1.ii) ทดสอบเทป-ไปยังคำสั่งถัดไป หรือ (2.ii) เลื่อนเทปซ้าย/เลื่อนเทปขวา/ไม่ทำอะไรเลย ตามด้วย (2.ii) ทดสอบเทป-ไปยังคำสั่งถัดไป แต่ Kleene สังเกตว่าในขณะที่
- "ที่จริงแล้ว อาจกล่าวได้ว่าการกระทำของเครื่องจักรทัวริงนั้นซับซ้อนอยู่แล้ว และประกอบด้วยกระบวนการทางจิตวิทยา ได้แก่ การพิมพ์และการเปลี่ยนแปลงสภาวะจิตใจ ตามด้วยการเคลื่อนไหวและสภาวะจิตใจอีกแบบหนึ่ง [และ] หลังปี 1947 จึงแยกการกระทำของทัวริงออกเป็นสองส่วน แต่ในที่นี้เราไม่ได้ทำเช่นนั้น ส่วนใหญ่เป็นเพราะการไม่ทำเช่นนั้นจะช่วยประหยัดพื้นที่ในตารางเครื่องจักร" (Kleene หน้า 379)