Кертис-Хедлунд-Линдон теоремасы - Curtis–Hedlund–Lyndon theorem

The Кертис-Хедлунд-Линдон теоремасы математикалық болып табылады сипаттама туралы ұялы автоматтар олардың тұрғысынан символикалық динамика. Оған байланысты Мортон Л.Кертис, Густав А. Хедлунд, және Роджер Линдон; өзінің теоремасы туралы 1969 жылғы мақаласында Хедлунд Кертис пен Линдонды бірге ашқан деп есептеді.[1] Ол «символикалық динамикадағы негізгі нәтижелердің бірі» деп аталды.[2]

Теорема а-дан функция деп айтады ауысым кеңістігі өзіне білдіреді ауысу функциясы егер ол болса ғана бір өлшемді ұялы автоматтың үздіксіз (қатысты Кантор топологиясы ) және эквивариант (ауысым картасына қатысты). Жалпы, бұл деп санайды морфизмдер кез келген екі ауысым аралықтары арасында (яғни ауысыммен жүретін үздіксіз кескіндер) дәл жергілікті ереже бойынша біркелкі анықталатын кескіндер болады.

Хедлунд қағазындағы теореманың нұсқасы тек бір өлшемді ақырлы автоматтарға қатысты, ал жоғары өлшемді жалпылау бүтін торлар көп ұзамай жарияланған Ричардсон (1972),[3] және оны торлардан бастап одан әрі жалпылауға болады дискретті топтар. Теореманың маңызды нәтижелерінің бірі - бұл қайтымды ұялы автоматтар, автоматтың кері динамикасын ұялы автоматты сипаттауға болады.

Анықтамалар

Ан алфавит - бұл а-дағы ұяшықтардың күйі деп ойлауға болатын кез-келген ақырлы жиынтық жиынтығы ұялы автомат. A конфигурация Бұл екі шексіз реттілік алфавиттегі белгілер:

..., х−2, х−1, х0, х1, х2, ....

A позиция конфигурацияда бүтін, реттік таңбалардың біреуінің индексі; позицияларды ұялы автоматтың жасушалары деп санауға болады. A өрнек - бұл позициялардың ақырлы жиынтығы және осы позициялардың әрқайсысына шартты белгілер тағайындау.

The ауысым кеңістігі - бұл берілген алфавит бойынша барлық мүмкін конфигурациялардың жиынтығы. Оған a құрылымы берілуі мүмкін топологиялық кеңістік сәйкес Кантор топологиясы, онда негізгі ашық жиындар кез-келген бір үлгіге сәйкес келетін конфигурация жиынтығы болып табылады және ашық жиынтықтар іргелі ашық жиындардың ерікті одақтары болып табылады. Бұл топологияда а функциясы f конфигурациядан конфигурацияға дейін үздіксіз егер, кез-келген бекітілген үлгі үшін б негізгі ашық жиынтықты анықтау P, жиынтық f−1(P) кескінделген конфигурациялар туралы f ішіне P өзін (мүмкін шексіз) жиынтықпен сипаттауға болады S өрнектер, конфигурацияға жататын қасиеті бар f−1(P) егер ол тек егер үлгіге сәйкес келсе ғана S.

The ауысым картасы белгілі бір үздіксіз функция болып табылады с конфигурацияны өзгертетін ауысым кеңістігінде х жаңа конфигурацияға ж онда әрбір таңба алдыңғы позициядан бір позицияға ауыстырылады: яғни әрбір бүтін сан үшін мен, жмен = хмен − 1. Функция f болып табылады эквивариант ауысым картасының астында, егер конфигурациялар бойынша түрлендіру сипатталса f ауысым картасымен жүру; яғни әрбір конфигурация үшін х, бұл солай болуы керек f(с(х)) = с(f(х)). Интуитивті түрде, бұл конфигурацияның кез-келген позициясы жаңартылатындығын білдіреді f барлық ережелер сияқты ережені қолдану.

A ұялы автомат конфигурацияның барлық позициялары бірдей жаңарту ережесінің негізінде бір уақытта жаңартыла отырып, позицияны қоршап тұрған алдын-ала тіркелген ақырлы маңындағы ұяшықтардың мәндеріне негізделген конфигурациядағы әрбір позицияның жаңа мәнін есептеу ережесімен анықталады. Яғни, позицияның жаңа мәні - бұл алдыңғы конфигурациядағы ұяшықтардың шектеусіз санына тәуелді болғаннан гөрі, оның маңындағы ұяшықтардың мәндерінің функциясы. Функция f ұялы автоматтың конфигурациясын оның ізбасарының конфигурациясымен салыстыру үшін осы ережені қолданатын, барлық позициялар бірдей жаңарту ережесін пайдаланады деген болжаммен ауысым картасына қатысты эквивариантты болады. Ол кантор топологиясында міндетті түрде үздіксіз болады: егер б - бұл негізгі ашық жиынтықты анықтайтын тұрақты үлгі P, содан кейін f−1(P) шектес өрнектер жиынтығымен анықталады, олардың маңындағы ұяшықтарға арналған тапсырмалар б бұл себеп f шығару б. Кертис-Хедлунд-Линдон теоремасында бұл екі қасиет ұялы автоматтарды анықтау үшін жеткілікті: кез-келген үздіксіз эквивариант функциясы - бұл ұялы автоматты жаңарту ережесі.

Дәлел

Чечерини-Сильберштейн және Корнаерт Кертис-Хедлунд-Линдон теоремасының келесі дәлелі болып табылады.[4]

Айталық f ауысу кеңістігіндегі үздіксіз ауысым-эквивариант функциясы. Әр конфигурация үшін х, рұқсат етіңіз б нүктесінде пайда болатын жалғыз таңбадан тұратын өрнек болуы керек f(х).Үздіксіздігі бойынша f, ақырлы үлгі болуы керек q жылы х егер сырттағы позициялар болса q ерікті түрде өзгертіледі, бірақ ішіндегі позициялар q олардың мәндеріне бекітілген х, содан кейін қолдану нәтижесі f нөл күйінде өзгеріссіз қалады. Эквивалентті түрде іргелі ашық жиынтық болуы керек Qх осындай х тиесілі Qх және әрбір конфигурация үшін ж жылы Qх, f(х) және f(ж) нөл күйінде бірдей мәнге ие болыңыз. Бұл іргелі ашық жиынтықтар Qх (барлық мүмкін конфигурациялар үшін) х) қалыптастыру ашық қақпақ ауысым кеңістігі. Алайда, ауысым кеңістігі a ықшам кеңістік: бұл алфавиті бар ақырғы топологиялық кеңістіктердің өнімі, сондықтан олардың ықшамдығы Тихонофф теоремасы. Ықшамдық бойынша кез-келген ашық мұқабада ақырғы ішкі жамылғы болады. Осы шектеулі ішкі мұқабада пайда болатын ақырғы позициялар жиынтығы сипаттамада нөлдік позицияның маңайы ретінде пайдаланылуы мүмкін f ұялы автомат ережесі ретінде.

Бүтін позициялар жиыны кез келгенімен ауыстырылған кезде дәл осындай дәлел жалпыға бірдей қолданылады дискретті топ G, конфигурациялар кеңістігі бастап функциялар жиынтығымен ауыстырылады G ақырлы алфавитке, ал ауысым-эквиваленттілік астындағы эквивариантпен ауыстырылады әрекет туралы G өздігінен. Атап айтқанда, бұл кез-келген өлшемдегі бүтін торда анықталған ұялы автоматтарға қатысты.

Шексіз алфавиттерге қарсы мысал

Бүтін сандардың екі шексіз тізбегінің кеңістігін қарастырып, функциясын анықтаңыз f осы кеңістіктен өзіне дейінгі ережеге сәйкес, егер f(х) = ж, содан кейін әр позиция үшін мен, жмен = хмен + хмен. Бұл ереже әр позиция үшін бірдей, сондықтан ол ауысымдық-эквивариантты болады. Кантор топологиясына сәйкес оны үздіксіз көрсетуге болады: әр ақырғы өрнек үшін б жылы ж, үлгісі бар х ең көп дегенде екі есе көп позициялармен f генерациялау б, ұяшықтардан тұрады б мәндері көшірілетін ұяшықтармен бірге б. Алайда, үздіксіз және эквивалентті болғанына қарамастан, f ұялы автоматты ереже емес, өйткені кез-келген ұяшықтың мәні кез-келген алдын-ала бекітілген шектелген ұяшықтарға байланысты емес, кез-келген басқа ұяшықтың мәніне тәуелді болуы мүмкін.[4]

Қайтарылатын ұялы автоматтарға қолдану

Ұялы автомат деп аталады қайтымды автоматтың әрбір конфигурациясы дәл бір предшественникке ие болған кезде. Әр конфигурацияны бұрынғыға дейін бейнелейтін функция ығысу кеңістігінде өзі үздіксіз болатындығы және ол ауысым-инвариантты екендігі ықшам аргументтен туындайды. Демек, Кертис-Хедлунд-Линдон теоремасы бойынша ұялы автоматтың уақыт бойынша кері динамикасы басқа ұялы автоматтар ережесінің көмегімен жасалуы мүмкін.[3] Алайда, кері автоматтағы ұяшықтың маңы алдыңғы автоматтағы сол ұяшықтың маңайынан едәуір үлкен болуы мүмкін.[5][6]

Жалпылау

Ұялы автоматтың анықтамасын позицияны қоршаған ақырғы, бірақ айнымалы көршілес ұяшықтардың мәндеріне негізделген конфигурациядағы әрбір позицияның жаңа мәнін есептеу ережелерімен анықталатын карталарға жалпылауға болады. Бұл жағдайда, классикалық анықтамадағыдай, жергілікті ереже барлық ұяшықтар үшін бірдей, бірақ көршілес позиция айналасындағы конфигурацияның функциясы болып табылады.

Классикалық ұялы автомат емес, үздіксіз және ауысымдық-эквивариантты карта үшін жоғарыда келтірілген қарсы мысал жалпыланған ұялы автомат. Алфавит ақырлы болған кезде, жалпыланған ұялы автоматтардың анықтамасы ауысым кеңістігінің ықшамдылығына байланысты ұялы автоматтардың классикалық анықтамасымен сәйкес келеді.

Жалпы ұялы автоматтар ұсынған Соботтка және Гончалвес (2016) [7] мұнда олар үздіксіз ауысымдық-эквиваленттік карталарға сәйкес келеді.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Хедлунд, Густав А. (1969), «Эндоморфизмдер және ауысымның динамикалық жүйелерінің автоморфизмдері», Математикалық жүйенің теориясы, 3 (4): 320–375, дои:10.1007 / BF01691062.
  2. ^ Шунич, Зоран (2014), «Ұялы автоматтар мен топтар, Туллио Чечерини-Сильберштейн және Мишель Корнаерт (кітапқа шолу)», Американдық математикалық қоғамның хабаршысы, 51 (2): 361–366, дои:10.1090 / S0273-0979-2013-01425-3.
  3. ^ а б Ричардсон, Даниэль (1972), «Жергілікті түрлендірулермен Tessellations», Компьютерлік және жүйелік ғылымдар журналы, 6: 373–388, дои:10.1016 / S0022-0000 (72) 80009-6, МЫРЗА  0319678.
  4. ^ а б Чехерини-Сильберштейн, Туллио; Корнаерт, Мишель (2010), «Теорема 1.8.1 (Кертис-Хедлунд теоремасы)», Ұялы автоматтар және топтар, Математикадағы Springer Monographs, Springer-Verlag, б. 20, ISBN  978-3-642-14033-4.
  5. ^ Маргенштерн, Морис (2007), Гиперболалық кеңістіктегі жасушалық автоматтар - Том I, 1 том, Мұрағат замандастары, б. 134, ISBN  978-2-84703-033-4.
  6. ^ Кари, Джарко (2005), «Қайтымды ұялы автоматтар» (PDF), Тілдер теориясының дамуы, Информатикадағы дәрістер, 3572, Springer-Verlag, 2-23 бет, дои:10.1007/11505877_5.
  7. ^ Соботтка, Марсело; Гонсалвес, Даниэль (2016), Сырғымалы блок-кодтардың анықтамасы және Кертис-Хедлунд-Линдон теоремасы туралы ескерту, arXiv:1507.02180, Бибкод:2015arXiv150702180S.