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

อ่าน 4 นาที

การเลื่อนย่อยของประเภทจำกัด

ในทางคณิตศาสตร์ ซับชิฟต์ชนิดจำกัด ( Subshifts of finite type)คือปริภูมิการเลื่อน (shift space)ที่นิยามโดยเซตคำต้องห้ามจำนวนจำกัด

การเลื่อนย่อยของประเภทจำกัด

ในทางคณิตศาสตร์ ซับชิฟต์ชนิดจำกัด ( Subshifts of finite type)คือปริภูมิการเลื่อน (shift space)ที่นิยามโดยเซตคำต้องห้ามจำนวนจำกัด มีการใช้ซับชิฟต์เหล่านี้ในการจำลองระบบพลวัตโดยเฉพาะอย่างยิ่งเป็นวัตถุของการศึกษาในพลวัตเชิงสัญลักษณ์และทฤษฎีเออร์โกดิกนอกจากนี้ยังใช้อธิบายเซตของลำดับที่เป็นไปได้ทั้งหมดที่ดำเนินการโดยเครื่องสถานะจำกัด (finite-state machine ) ปริภูมิการเลื่อนที่ได้รับการศึกษาอย่างกว้างขวางที่สุดคือซับชิฟต์ชนิดจำกัด

ตัวอย่างที่สร้างแรงบันดาลใจ

ตัวอย่างหนึ่งของการเลื่อน (ด้านเดียว) ชนิดจำกัด คือ เซตของลำดับทั้งหมด ซึ่งอนันต์ที่ปลายด้านเดียวเท่านั้น ที่สามารถประกอบขึ้นจากตัวอักษรเช่นนี่เรียกว่าการเลื่อนแบบเต็มและใช้สัญลักษณ์แทน

โดยการห้ามใช้คำนั้นจะทำให้เกิดการเปลี่ยนแปลงประเภทจำกัดที่เรียกว่าการเปลี่ยนแปลงสีทอง (golden shift ) ซึ่งได้ชื่อนี้เพราะจำนวนคำที่ถูกต้องตามกฎหมายที่มีความยาวเท่ากับจำนวนฟิโบนาชชีการเปลี่ยนแปลงสองด้านประเภทจำกัดนั้นคล้ายกัน แต่ประกอบด้วยลำดับที่ไม่มีที่สิ้นสุดทั้งสองด้าน

ซับชิฟต์สามารถกำหนดได้ด้วยกราฟแบบมีทิศทางบนตัวอักษร เช่น กราฟโดยประกอบด้วยลำดับที่มีการเปลี่ยนผ่านระหว่างตัวอักษรที่อยู่ติดกันเฉพาะที่กราฟอนุญาตเท่านั้น สำหรับตัวอย่างนี้ ซับชิฟต์ประกอบด้วยลำดับด้านเดียวเพียงสามลำดับ: ในทำนองเดียวกัน ซับชิฟต์สองด้านที่อธิบายโดยกราฟนี้ประกอบด้วยลำดับสองด้านเพียงสามลำดับ

กราฟทิศทางอื่นๆ บนตัวอักษรเดียวกันจะสร้างการเลื่อนย่อยอื่นๆ ตัวอย่างเช่น การเพิ่มลูกศรอีกอันลงในกราฟจะสร้างการเลื่อนย่อยที่แทนที่จะมีลำดับสามลำดับ กลับมี ลำดับ จำนวนอนันต์ที่นับไม่ได้โดยที่การเข้ารหัสตัวอักษรในระดับท้องถิ่นไม่สามารถกำหนดได้ การเลื่อนย่อยทุกประเภทที่มีชนิดจำกัดสามารถอธิบายได้ด้วยกราฟทิศทางดังกล่าว

คำนิยาม

ให้เป็นเซตจำกัดของสัญลักษณ์ (ตัวอักษร) ให้แทนเซตของลำดับอนันต์คู่ทั้งหมดขององค์ประกอบของพร้อมกับตัวดำเนินการเลื่อนเรากำหนดโทโพโลยีแบบไม่ต่อเนื่องให้กับและโทโพโลยีแบบ ผลคูณ ให้กับ โฟล ว์เชิงสัญลักษณ์หรือการเลื่อนย่อยเป็นเซตย่อยที่ไม่เปลี่ยนแปลงภายใต้ปิดของ[ 1 ]และภาษาที่เกี่ยวข้องคือเซตของคำย่อยจำกัดขององค์ประกอบของ[ 2 ]

ให้เป็นเซตจำกัดของคำในอักษรซึ่งเรียกว่าคำต้องห้ามส่วนย่อยแบบจำกัดชนิดที่เกี่ยวข้องนั้น กำหนดให้เป็นปริภูมิ

ลำดับของคำที่หลีก เลี่ยงชุดคำต้องห้าม

ถ้าลำดับขยายไปสู่อนันต์ในทิศทางเดียวดังที่กล่าวมาข้างต้น จะเรียกว่า ซับชิฟต์ ด้านเดียวชนิดจำกัด และถ้าเป็นแบบสองด้านจะเรียกว่า ซับชิฟต์ สองด้านชนิดจำกัด

ตัวดำเนินการเลื่อน (shift operator) จะแปลงลำดับใน shift ด้านเดียวหรือสองด้านไปเป็นลำดับอื่นโดยการเลื่อนสัญลักษณ์ทั้งหมดไปทางซ้าย เช่น

เห็นได้ชัดว่าแผนที่นี้สามารถกลับด้านได้เฉพาะในกรณีของการเลื่อนสองด้านเท่านั้น

กลุ่มย่อยที่มีประโยชน์เป็นพิเศษอย่างหนึ่งคือการเลื่อนขอบให้Aเป็นเมทริกซ์ประชิดขนาดn × n ที่มีสมาชิกอยู่ใน{0, 1}โดยใช้สมาชิกเหล่านี้ เราสร้างกราฟทิศทางG = ( V , E )โดยที่Vคือเซตของจุดยอด และEคือเซตของขอบที่มีขอบทิศทางxyในEก็ต่อเมื่อA = 1ให้Yเป็นเซตของลำดับขอบที่ยอมรับได้ แบบอนันต์ทั้งหมด โดยที่ ยอมรับได้หมายความว่าลำดับนั้นเป็นการเดินของกราฟ และลำดับนั้นอาจเป็นอนันต์ด้านเดียวหรือสองด้านก็ได้ ให้Tเป็นตัวดำเนินการเลื่อนซ้ายบนลำดับดังกล่าว มันทำหน้าที่เป็นตัวดำเนินการวิวัฒนาการตามเวลาของระบบพลวัต การเลื่อนขอบจึงถูกกำหนดให้เป็นคู่( Y , T )ที่ได้มาด้วยวิธีนี้

ในทางทฤษฎี เราอาจกำหนดลำดับของขอบได้ดังนี้

นี่คือปริภูมิของลำดับสัญลักษณ์ทั้งหมด โดยที่สัญลักษณ์pจะตามด้วยสัญลักษณ์q ได้ ก็ต่อเมื่อ สมาชิกตัวที่ ( p , q )ของเมทริกซ์Aมีค่าเป็น 1 เท่านั้น ปริภูมิของลำดับอนันต์คู่ ทั้งหมด ถูกนิยามในทำนองเดียวกัน:

การเลื่อนขอบเป็นเซตย่อยของการเลื่อนย่อยประเภทจำกัดซึ่งเซตของคำต้องห้ามประกอบด้วยคำสองตัวอักษรเท่านั้น ในทางกลับกัน สามารถแสดงได้ว่าการเลื่อนย่อยประเภทจำกัดทุกรายการเป็นคู่กันทางโทโพโลยีกับการเลื่อนขอบผ่าน การเข้ารหัส ใหม่ในท้องถิ่น[ 3 ]

การเลื่อนขอบเรียกว่าแบบถ่ายทอดได้ (transitive)ถ้าGเป็น กราฟ ที่เชื่อมต่อกันอย่างแน่นหนา (strongly connected ) กล่าวคือ มีลำดับของขอบจากจุดยอดใดๆ ไปยังจุดยอดอื่นๆ การเลื่อนขอบย่อยแบบจำกัด (finite type) ที่มีวงโคจรหนาแน่น (dense orbits) คือการเลื่อนขอบย่อยที่เป็นคู่สม (conjugate) กับการเลื่อนขอบแบบถ่ายทอดได้นั่นเอง

กรณีพิเศษที่สำคัญคือn -shift แบบเต็ม : มันมีกราฟที่มีขอบที่เชื่อมต่อทุกจุดยอดกับทุกจุดยอดอื่น ๆ กล่าวคือ ค่าทั้งหมดในเมทริกซ์ประชิดเป็น 1 n -shift แบบเต็มสอดคล้องกับแบบแผนเบอร์นูลลีที่ไม่มีการวัด

ศัพท์เฉพาะ

ตามธรรมเนียมแล้ว คำว่า " shift"หมายถึง shift เต็มรูปแบบn- shift ส่วน subshiftคือ subspace ใดๆ ของ shift เต็มรูปแบบที่ไม่เปลี่ยนแปลงภายใต้การกระทำของตัวดำเนินการ shift (กล่าวคือ subspace ที่ไม่เปลี่ยนแปลงภายใต้การกระทำของตัวดำเนินการ shift) ไม่ว่างเปล่า และปิดสำหรับโทโพโลยีผลคูณที่กำหนดไว้ด้านล่าง subshift บางส่วนสามารถระบุลักษณะได้ด้วยเมทริกซ์การเปลี่ยนผ่าน ดังที่กล่าวมาข้างต้น subshift ดังกล่าวเรียกว่า subshift ประเภทจำกัด บ่อยครั้งที่ subshift ประเภทจำกัดเรียกว่าshift ประเภทจำกัดบางครั้ง subshift ประเภทจำกัดก็เรียกว่าtopological Markov shiftsด้วย

ตัวอย่าง

ระบบพลวัตอลวนจำนวนมากมีลักษณะสมมาตรกับซับชิฟต์ของชนิดจำกัด ตัวอย่างเช่น ระบบที่มีการเชื่อมต่อโฮโมคลินิกตามขวางการแปลงแบบดิฟเฟอเรนเชียลของแมนิโฟลด์ปิดที่ มี เอนโทรปีเมตริกเป็นบวกและแผนที่มาร์คอฟเชิงเส้นแบบแบ่งช่วงของช่วงเวลา

โทโพโลยี

ซับชิฟต์มีโทโพโลยีตามธรรมชาติ ซึ่งได้มาจากโทโพโลยีผลคูณบนโดยที่

และVได้รับโทโพโลยีแบบไม่ต่อเนื่องฐานสำหรับโทโพโลยีของซึ่งเหนี่ยวนำให้เกิดโทโพโลยีของการเลื่อนย่อย คือตระกูลของเซตทรงกระบอก

เซตทรงกระบอกเป็นเซตปิดและ เปิด ในเซตเปิดทุกเซตในเป็นการ รวมกันแบบ นับได้ของเซตทรงกระบอก เซตเปิดทุกเซตในซับชิฟต์เป็นการตัดกันของเซตเปิดของกับซับชิฟต์ เมื่อเทียบกับโทโพโลยีนี้ ชิฟต์Tเป็นโฮมีโอเมอร์ฟิซึม นั่นคือ เมื่อเทียบกับโทโพโลยีนี้ มันมีความต่อเนื่องและมีอินเวอร์สที่ต่อเนื่อง

พื้นที่ดังกล่าวมีลักษณะสมมาตรกับเซตแคนเตอร์

เมตริก

สามารถกำหนดเมตริกที่แตกต่างกันได้หลากหลายบนปริภูมิการเลื่อน เราสามารถกำหนดเมตริกบนปริภูมิการเลื่อนได้โดยพิจารณาว่าจุดสองจุดนั้น "อยู่ใกล้กัน" หากมีสัญลักษณ์เริ่มต้นร่วมกันจำนวนมาก นี่คือเมตริกp -adic อันที่จริงแล้ว ทั้งปริภูมิการเลื่อนด้านเดียวและสองด้านต่างก็เป็นปริภูมิเมตริกแบบกะทัดรัด

วัด

การเลื่อนย่อยแบบจำกัดประเภทอาจได้รับมอบหมายด้วยมาตรวัด ที่แตกต่างกันหลายแบบ ซึ่งนำไปสู่ระบบพลวัตที่รักษามาตรวัดไว้วัตถุที่นิยมศึกษาโดยทั่วไปคือมาตรวัดมาร์คอฟซึ่งเป็นการขยายลูกโซ่มาร์คอฟไปยังโทโพโลยีของการเลื่อน

ห่วงโซ่มาร์คอฟคือคู่( P , π)ที่ประกอบด้วย เมทริก ซ์การเปลี่ยนสถานะเมทริกซ์n × n P = ( p )ซึ่งp ทั้งหมด ≥ 0และ

สำหรับทุกiเวกเตอร์ความน่าจะเป็นคงที่π = ( π ) มีค่า π 0ทั้งหมดและมี

กล่าวได้ว่าโซ่ Markov ตามที่นิยามไว้ข้างต้นนั้นเข้ากันได้กับการเลื่อนแบบจำกัดประเภท ถ้าp = 0เมื่อใดก็ตามที่A = 0 จากนั้น มาตรวัด Markovของเซตทรงกระบอกอาจนิยามได้โดย

เอนโทรปี ของKolmogorov–Sinaiที่สัมพันธ์กับการวัดแบบ Markov คือ

การวัดแบบมาร์คอฟและแบบไม่มาร์คอฟ

ส่วนที่ซ่อนอยู่ของแบบจำลองมาร์คอฟแบบซ่อนเร้น ซึ่งสถานะที่สังเกตได้ไม่ใช่แบบมาร์คอฟ

ดังที่กล่าวมาข้างต้น เมื่อกำหนดเมทริกซ์การเปลี่ยนสถานะของมาร์คอฟและการกระจายแบบไม่เปลี่ยนแปลงบนสถานะต่างๆ เราสามารถกำหนดมาตรวัดความน่าจะเป็นบนซับชิฟต์ได้ ตัวอย่างเช่น พิจารณาโซ่มาร์คอฟที่แสดงทางด้านซ้ายบนสถานะต่างๆโดยมีการกระจายแบบไม่เปลี่ยนแปลงหากเรา "ลืม" ความแตกต่างระหว่างเราจะฉายซับชิฟต์นี้บนไปยังซับชิฟต์บนและการฉายภาพนี้ยังฉายมาตรวัดความน่าจะเป็นลงไปยังมาตรวัดความน่าจะเป็นบนซับชิฟต์บนด้วย

สิ่งที่น่าสนใจคือ การวัดความน่าจะเป็นบนการเลื่อนย่อยบนไม่ได้ถูกสร้างขึ้นโดยห่วงโซ่ Markov บนแม้แต่ลำดับหลายลำดับก็ตาม โดยสัญชาตญาณแล้ว นี่เป็นเพราะว่า หากสังเกตลำดับยาวของแล้วจะมีความมั่นใจมากขึ้นเรื่อยๆ ว่า ซึ่งหมายความว่าส่วนที่สังเกตได้ของระบบอาจได้รับผลกระทบจากบางสิ่งบางอย่างในอดีตอันไม่มีที่สิ้นสุด[ 4 ] [ 5 ]

ในทางกลับกัน มีการเลื่อนย่อยบนสัญลักษณ์ 6 ตัว ซึ่งฉายไปยังการเลื่อนย่อยบนสัญลักษณ์ 2 ตัว โดยที่การวัดแบบมาร์คอฟใดๆ บนการเลื่อนย่อยที่เล็กกว่าจะมีการวัดแบบพรีอิมเมจที่ไม่ใช่แบบมาร์คอฟในลำดับใดๆ (ตัวอย่าง 2.6 [ 5 ] )

ฟังก์ชันซีตา

ฟังก์ชันซีตา ของArtin–Mazurถูกกำหนดให้เป็นอนุกรมกำลังอย่างเป็นทางการ

โดยที่Fix( T n )คือเซตของจุดคงที่ของ การเลื่อน nเท่า[ 6 ] มีสูตรผลคูณ

โดยที่γวิ่งผ่านวงโคจรปิด[ 6 ] สำหรับการเลื่อนย่อยประเภทจำกัด ฟังก์ชันซีตาเป็นฟังก์ชันตรรกยะของz : [ 7 ]

การสรุปโดยทั่วไป

การเปลี่ยนแบบโซฟิกคือภาพของการเปลี่ยนย่อยประเภทจำกัดซึ่งขอบที่แตกต่างกันของกราฟการเปลี่ยนผ่านอาจถูกแมปไปยังสัญลักษณ์เดียวกัน ตัวอย่างเช่น หากเราดูเฉพาะเอาต์พุตจากห่วงโซ่มาร์คอฟที่ซ่อนอยู่ เอาต์พุตจะปรากฏเป็นระบบโซฟิก[ 4 ]อาจถือได้ว่าเป็นเซตของการติดป้ายกำกับเส้นทางผ่านออโตมาตอน : การเปลี่ยนย่อยประเภทจำกัดจึงสอดคล้องกับออโตมาตอนที่เป็นแบบกำหนดได้ [ 8 ] ระบบดังกล่าวสอดคล้องกับภาษาปกติ

ระบบที่ไม่ขึ้นกับบริบทนั้นถูกนิยามในลักษณะเดียวกัน และถูกสร้างขึ้นโดยใช้ไวยากรณ์โครงสร้างวลี

ระบบการต่ออายุถูกนิยามว่าเป็นเซตของการต่อกันอย่างไม่มีที่สิ้นสุดทั้งหมดของชุดคำจำกัดจำนวนคงที่ชุดหนึ่ง

ซับชิฟต์ชนิดจำกัดนั้นเหมือนกับโมเดลพ็อตส์ แบบหนึ่งมิติอิสระ (ไม่เกิดปฏิสัมพันธ์) ( ซึ่งเป็นการวางนัยทั่วไปของโมเดลไอซิง ด้วยตัวอักษร n ตัว ) โดยไม่รวมการกำหนดค่าเพื่อนบ้านที่ใกล้ที่สุดบางส่วน โมเดลไอซิงที่เกิดปฏิสัมพันธ์นั้นถูกกำหนดให้เป็นซับชิฟต์ร่วมกับฟังก์ชันต่อเนื่องของปริภูมิการกำหนดค่า(ต่อเนื่องเมื่อเทียบกับโทโพโลยีผลคูณ ซึ่งกำหนดไว้ด้านล่าง) ฟังก์ชันพาร์ติชันและแฮมิลโทเนียนสามารถแสดงได้อย่างชัดเจนในรูปของฟังก์ชันนี้

การเลื่อนย่อยอาจถูกทำให้เป็นควอนตัมด้วยวิธีใดวิธีหนึ่ง ซึ่งนำไปสู่แนวคิดของออโตมาตาจำกัดควอนตั

ดูเพิ่มเติม

หมายเหตุ

  1. Xie (1996) หน้า 21
  2. Xie (1996) หน้า 22
  3. Lind, Douglas A.; Marcus, Brian (1995). บทนำสู่พลวัตเชิงสัญลักษณ์และการเข้ารหัส . เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 9780511626302.
  4. 1 2 การวัดแบบโซฟิก: ลักษณะเฉพาะของห่วงโซ่มาร์คอฟที่ซ่อนอยู่โดยพีชคณิตเชิงเส้น ภาษาเชิงรูปธรรม และพลวัตเชิงสัญลักษณ์ - คาร์ล ปีเตอร์เซน, คณิตศาสตร์ 210, ภาคเรียนฤดูใบไม้ผลิ ปี 2549, มหาวิทยาลัยนอร์ทแคโรไลนา แชเปลฮิลล์
  5. 1 2 Boyle, Mike; Petersen, Karl (2010-01-13), กระบวนการมาร์คอฟที่ซ่อนอยู่ในบริบทของพลวัตเชิงสัญลักษณ์ , arXiv : 0907.1858
  6. 1 2 Brin & Stuck (2002) หน้า 60
  7. Brin & Stuck (2002) หน้า 61
  8. ไพเทียส ฟอกก์ (2002) หน้า 205

เอกสารอ้างอิง

อ่านเพิ่มเติม

  • วิลเลียมส์, ซูซาน จี., บรรณาธิการ (2004). พลศาสตร์เชิงสัญลักษณ์และการประยุกต์ใช้: สมาคมคณิตศาสตร์อเมริกัน, หลักสูตรระยะสั้น, 4-5 มกราคม 2002, ซานดิเอโก, แคลิฟอร์เนีย . เอกสารประกอบการบรรยายหลักสูตรระยะสั้นของ AMS เล่มที่ 60. สมาคมคณิตศาสตร์อเมริกัน . ISBN 0-8218-3157-7. Zbl 1052.37003 . 

สรุปเนื้อหา

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

ข้อมูลสำคัญเกี่ยวกับ การเลื่อนย่อยของประเภทจำกัด

ในทางคณิตศาสตร์ ซับชิฟต์ชนิดจำกัด ( Subshifts of finite type)คือปริภูมิการเลื่อน (shift space)ที่นิยามโดยเซตคำต้องห้ามจำนวนจำกัด

ตัวอย่างที่สร้างแรงบันดาลใจ

ตัวอย่างหนึ่งของการเลื่อน (ด้านเดียว) ชนิดจำกัด คือ เซตของลำดับทั้งหมด ซึ่งอนันต์ที่ปลายด้านเดียวเท่านั้น ที่สามารถประกอบขึ้นจากตัวอักษรเช่นนี่เรียกว่าการเลื่อนแบบเต็มและใช้สัญลักษณ์แทนเอ,บี{\displaystyle A,B}เอเอเอ⋯,เอบีเอบี⋯,…{\displaystyle AAA\cdots...

คำนิยาม

ให้เป็นเซตจำกัดของสัญลักษณ์ (ตัวอักษร) ให้แทนเซตของลำดับอนันต์คู่ทั้งหมดขององค์ประกอบของพร้อมกับตัวดำเนินการเลื่อนเรากำหนดโทโพโลยีแบบไม่ต่อเนื่องให้กับและโทโพโลยีแบบ ผลคูณ ให้กับ โฟล ว์เชิงสัญลักษณ์หรือการเลื่อนย่อยเป็นเซตย่อยที่ไม่เปลี่ยนแปลงภายใต้ปิดของ[ 1...

ศัพท์เฉพาะ

ตามธรรมเนียมแล้ว คำว่า " shift"หมายถึง shift เต็มรูปแบบn- shift ส่วน subshiftคือ subspace ใดๆ ของ shift เต็มรูปแบบที่ไม่เปลี่ยนแปลงภายใต้การกระทำของตัวดำเนินการ shift (กล่าวคือ subspace ที่ไม่เปลี่ยนแปลงภายใต้การกระทำของตัวดำเนินการ shift) ไม่ว่างเปล่า...