กลับไปหน้าบทความ

อ่าน 2 นาที

หวัง บี-แมชชีน

ตามที่ Hao Wang (1954, 1957) นำเสนอ เครื่องจักรพื้นฐาน B ของเขา เป็นแบบจำลองการคำนวณที่เรียบง่ายอย่างยิ่งเทียบเท่ากับ เครื่องจักรทัวริง มันคือ...

หวัง บี-แมชชีน

ตามที่ Hao Wang (1954, 1957) นำเสนอเครื่องจักรพื้นฐาน B ของเขา เป็นแบบจำลองการคำนวณที่เรียบง่ายอย่างยิ่งเทียบเท่ากับเครื่องจักรทัวริงมันคือ "การกำหนดทฤษฎีเครื่องจักรทัวริงครั้งแรกในแง่ของแบบจำลองที่คล้ายคอมพิวเตอร์" (Minsky, 1967: 200) ด้วยคำสั่งเรียงลำดับเพียง 4 คำสั่ง มันจึงคล้ายคลึงกับ แต่เรียบง่ายกว่า คำสั่งเรียงลำดับ 7 คำสั่งของเครื่องจักรหลังทัวริงในบทความเดียวกัน Wang ได้แนะนำเครื่องจักรที่เทียบเท่ากันหลายประเภท รวมถึงสิ่งที่เขาเรียกว่าเครื่องจักร Wซึ่งก็คือเครื่องจักร B ที่เพิ่มคำสั่ง "ลบ" เข้าไปในชุดคำสั่ง

คำอธิบาย

ตามที่ Wang (1954) กำหนดไว้ เครื่อง B มีคำสั่งเพียง 4 คำสั่งเท่านั้น: [ 1 ]

  1.  : เลื่อนหัวสแกนเทปไปทางขวาหนึ่งช่อง (หรือเลื่อนเทปไปทางซ้ายหนึ่งช่อง) จากนั้นดำเนินการต่อตามคำสั่งถัดไปตามลำดับตัวเลข
  2.  : เลื่อนหัวสแกนเทปไปทางซ้ายหนึ่งช่อง (หรือเลื่อนเทปไปทางขวาหนึ่งช่อง) จากนั้นดำเนินการต่อตามคำสั่งถัดไปตามลำดับตัวเลข
  3. *  : ในเทปที่สแกนแล้วจะมีเครื่องหมาย * พิมพ์อยู่ จากนั้นให้ไปที่คำสั่งถัดไปตามลำดับตัวเลข
  4. C n: การ "โอนย้าย" (กระโดด, แยกสาขา) แบบมีเงื่อนไขไปยังคำสั่ง "n": ถ้าช่องเทปที่สแกนถูกทำเครื่องหมาย ให้ไปที่คำสั่ง "n" มิฉะนั้น (ถ้าช่องที่สแกนว่างเปล่า) ให้ดำเนินการต่อในคำสั่งถัดไปตามลำดับตัวเลข

ตัวอย่างคำสั่ง B-machine แบบง่ายๆ คือตัวอย่างของเขา: [ 2 ]

1. *, 2. →, 3. C2, 4. →, 5. ←

เขาเขียนใหม่โดยใช้รูปแบบเป็นชุดคู่ลำดับ:

{ ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }

เครื่อง W ของ Wang นั้นก็คือเครื่อง B ที่เพิ่มคำสั่งอีกหนึ่งคำสั่งเข้าไปนั่นเอง

5.   E  : ในช่องเทปที่สแกนแล้ว ให้ลบเครื่องหมาย * (ถ้ามี) จากนั้นไปที่คำสั่งถัดไปตามลำดับตัวเลข

ดูเพิ่มเติม

หมายเหตุ

  1. ^หวัง 1957หน้า 64
  2. ^หวัง 1957หน้า 65
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Wang_B-machine&oldid=1331045470 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ หวัง บี-แมชชีน

ตามที่ 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 "