อ่าน 2 นาที
หวัง บี-แมชชีน
ตามที่ Hao Wang (1954, 1957) นำเสนอ เครื่องจักรพื้นฐาน B ของเขา เป็นแบบจำลองการคำนวณที่เรียบง่ายอย่างยิ่งเทียบเท่ากับ เครื่องจักรทัวริง มันคือ...
หวัง บี-แมชชีน
ตามที่ Hao Wang (1954, 1957) นำเสนอเครื่องจักรพื้นฐาน B ของเขา เป็นแบบจำลองการคำนวณที่เรียบง่ายอย่างยิ่งเทียบเท่ากับเครื่องจักรทัวริงมันคือ "การกำหนดทฤษฎีเครื่องจักรทัวริงครั้งแรกในแง่ของแบบจำลองที่คล้ายคอมพิวเตอร์" (Minsky, 1967: 200) ด้วยคำสั่งเรียงลำดับเพียง 4 คำสั่ง มันจึงคล้ายคลึงกับ แต่เรียบง่ายกว่า คำสั่งเรียงลำดับ 7 คำสั่งของเครื่องจักรหลังทัวริงในบทความเดียวกัน Wang ได้แนะนำเครื่องจักรที่เทียบเท่ากันหลายประเภท รวมถึงสิ่งที่เขาเรียกว่าเครื่องจักร Wซึ่งก็คือเครื่องจักร B ที่เพิ่มคำสั่ง "ลบ" เข้าไปในชุดคำสั่ง
คำอธิบาย
ตามที่ Wang (1954) กำหนดไว้ เครื่อง B มีคำสั่งเพียง 4 คำสั่งเท่านั้น: [ 1 ]
- → : เลื่อนหัวสแกนเทปไปทางขวาหนึ่งช่อง (หรือเลื่อนเทปไปทางซ้ายหนึ่งช่อง) จากนั้นดำเนินการต่อตามคำสั่งถัดไปตามลำดับตัวเลข
- ← : เลื่อนหัวสแกนเทปไปทางซ้ายหนึ่งช่อง (หรือเลื่อนเทปไปทางขวาหนึ่งช่อง) จากนั้นดำเนินการต่อตามคำสั่งถัดไปตามลำดับตัวเลข
- * : ในเทปที่สแกนแล้วจะมีเครื่องหมาย * พิมพ์อยู่ จากนั้นให้ไปที่คำสั่งถัดไปตามลำดับตัวเลข
- C n: การ "โอนย้าย" (กระโดด, แยกสาขา) แบบมีเงื่อนไขไปยังคำสั่ง "n": ถ้าช่องเทปที่สแกนถูกทำเครื่องหมาย ให้ไปที่คำสั่ง "n" มิฉะนั้น (ถ้าช่องที่สแกนว่างเปล่า) ให้ดำเนินการต่อในคำสั่งถัดไปตามลำดับตัวเลข
ตัวอย่างคำสั่ง B-machine แบบง่ายๆ คือตัวอย่างของเขา: [ 2 ]
- 1. *, 2. →, 3. C2, 4. →, 5. ←
เขาเขียนใหม่โดยใช้รูปแบบเป็นชุดคู่ลำดับ:
- { ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }
เครื่อง W ของ Wang นั้นก็คือเครื่อง B ที่เพิ่มคำสั่งอีกหนึ่งคำสั่งเข้าไปนั่นเอง
- 5. E : ในช่องเทปที่สแกนแล้ว ให้ลบเครื่องหมาย * (ถ้ามี) จากนั้นไปที่คำสั่งถัดไปตามลำดับตัวเลข
ดูเพิ่มเติม
หมายเหตุ
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ หวัง บี-แมชชีน
ตามที่ Hao Wang (1954, 1957) นำเสนอ เครื่องจักรพื้นฐาน B ของเขา เป็นแบบจำลองการคำนวณที่เรียบง่ายอย่างยิ่งเทียบเท่ากับ เครื่องจักรทัวริง มันคือ...
คำอธิบาย
ตามที่ Wang (1954) กำหนดไว้ เครื่อง B มีคำสั่งเพียง 4 คำสั่งเท่านั้น: [ 1 ]
ดูเพิ่มเติม
ออโตมาตาเซลลูลาร์ของค็อดด์ รุ่นเครื่องนับ
หมายเหตุ
^ หวัง 1957 หน้า 64 ^ หวัง 1957 หน้า 65 ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Wang_B-machine&oldid=1331045470 "