Показивачка машина

У теоријском рачунарству, показивачка машина представља "атомистички" апстрактни машински модел рачунања налик на машину са случајним приступом.

У зависности од врсте, показивачка машина се може назвати и повезујућим аутоматом, КУ-машином, СММ, атомистичком ЛИСП масином, дрво-показивачком машином итд. Најмање три главне врсте постоје у литератури - Колмогоров-Успенски модел(КУМ, КУ-машина), Кнут повезивајући аутомат, и Шонхагов модел машине за модификацију складишта (СММ). СММ је најчешћи. Машина прима улазне податке са траке "само за читање", секвенце симбола направљене од бар два симбола, нпр. 0 и 1, и пише излазне податке на траку "само за писање". Да би трансформисала секвенцу симбола, тј. улазне податке у секвенцу симбола као излазне податке, машина поседује "програм" - машину коначног стања, коју чини меморија и листа инструкција. Преко свог стања машина програм чита улазне симболе, оперише на својој структури за складиштење - колекцији чворова(регистара) међусобно повезаних "гранама" (показивачима означеним симболима нпр. 0,1) и пише симболе на излазној траци.

Показивачка машина не може да врши аритметичке операције. Рачунање се своди на читање улазних симбола, њихову измену, обављање разних тестова на структури складишта - шаблоне чворова и показивача, и излаз симбола на основу тестова. "Информација" се налази у складишној структури.

Типови показивачке машине

I Гуревиц и Бен-Амрам су направили листу веома сличних атомских модела апстрактних машина. Бен-Амрам верује да постоје атомски модели (којих има шест) и модели вишег нивоа. Три главна атомска модела су:

• Шонхагов модел машине са модификацијом складишта
• Колмогоров-Успенски машине
• Кнутов повезивајући аутомат

Али Бен-Амрам додаје и:

• Атомистичку "искључиво-ЛИСП" машину
• Атомистичку "потпуно-ЛИСП" машину
• Генералну атомистичку показивачку машину
• Јоне'с I језик - два типа

Проблеми модела показивачке машине

Употреба модела у теорији комплексности: ван Емде Боас (1990) изражава забринутост да овај облик апстрактног модела: "да је интересантни теоријски модел, али његова привлачност као фундаменталног модела за теорију комплексности је под знаком питања. Његова мера времена се базира на униформном времену у контексту да ова мера потцењује праву временску комплексност"

Гуревиц 1988. године такође изражава забринутост:

"...прагматично гледано, Сцхонаге модел даје добру меру сложености времена што се тиче тренутног напретка...иако бих волео нешто слично рачунарима са случајним приступом Англуина и Валијанта", чиме мисли на Англуин D. и Валиант L.Г., "Брзи пробабилистички алгоритми за хамилтонске кругове и поклапања". Чињеница је да Сцхоинагег сам демонстрира еквиваленције у реалном времену своје две машине са случајним приступом, моделе "РАМ0" и "РАМ1", што води до питања неопходности СММ за студије комплексности.

Могућа коришћења модела

Ипак, Сцхонаге описује множење целих бројева у линеарном временуу, а Гуревиц се пита да ли паралелна КУ масина подсећа на људски мозак.

Шонхагова машина модификације складишта - модел СММ

Чини се да је Шонхагов СММ модел најчешћи и највише прихваћен. Сасвим је различит од модела регистарске машине и других уобичајених рачунских модела, као што су Турингова машина на бази траке или означене рупе на бројачкој машини.

Рачунар се састоји од фиксног алфабета улазних симбола, и променљивог усмереног графа, тј. дијаграма стања, са стрелицама означеним симболима алфабета. Сваки чвор графа има тачно једну излазну стрелицу означену сваким симболом, иако се неке од њих враћају у оригинални чвор. Један фиксирани чвор графа је означен као почетни чвор.

Свака реч симбола у алфабету се може превести као пут кроз машину. нпр. 10011 се може превести као пут 1 од почетног чвора затим пут 0 од крањњег чвора, затим пут 1, па пут 1, па пут 1. Пут се може идентификовати као резултујући чвор, али идентификација ће се мењати како се граф мења у току рачунања.

Машина може да прими инструкције које мењају изглед графа. Основне инструкције су нове w инструкције, које креирају нови чвор који је резултат низа w, а скуп w до в инструкција који поново усмерава грану до другог чвора. Овде w и в представљају речи, в је претходна реч нпр. претходно направљени низ симбола, тако да поново усмерена грана показује уназад ка старом чвору који је резултат тог низа.

Кораци у креирању новог чвора у машини са два симбола {0,1}

Када се сусретнемо са новом речи, што је у овом случају 11, машина је одговорна за креирање новог чвора 3 и показује одговарајућу грану ка њему, затим креира два нова показивача, оба показују назад ка старом чвору, што је у овом примеру 2.

(1) нови w: прави нови чвор. W представља нову реч која прави нови чвор. Машина чита реч w, затим пут представљен симболима w док машина не дође до последњег, "додатног" симбола у речи. Додатни симбол приморава последње стање да направи нови чвор, и обрће одговарајућу стрелицу (означену тим симболом) са старе позиције да показује на нови чвор. Нови чвор обрће све гране назад на последње стање, када су биле неусмерене, смислу да нови чворови "спавају", чекајући на доделу. У случају почетног чвора такође ћемо почети са обе гране које показују назад ка себи.

Нпр. нека је "w" 10110[1], где је финални карактер у загради како би означио свој посебни статус. Узимамо грану 1 чвора да показује на нови, 7. чвор. Две гране овог чвора затим показују назад на 6. чвор.

(2) скуп w до в: померити грану(стрелицу) од пута представљеног речју w до претходног чвора представљеног речју в. Опет је последња стрелица у путу та која ће бити преусмерена.

Пример: скуп 1011011 на 1011, након инструкције изнад, промениће 1 стрелицу новог чвора на 101101 да покаже на пети чвор на путу, достигнут 1011. Онда би пут 1011011 имао исти резултат као 1011.

(3) ако је в=w, онда инструкција з: Условна инструкција која упоређује два пута представљена речима w и в да види да ли се завршавају у истом чвору. Ако је то тачно, пређи на инструкцију з; ако није тачно, настави. Ова инструкција има исту сврху као и њен пандан у регистарској или Wанг-б машини, што одговара способности Турингове машине да пређе на следеће стање.

Кнутов модел повезивајућег аутомата

Према Шонхагеу, Кнут је навео да се СММ модел поклапа са специјалним типом повезивајућег аутомата укратко објашњеног у књизи "Тхе арт оф цомпутер программинг".

Колмогоров - Успенски модел машине - КУ машина

КУМ се разликује од СММ у томе што дозвољава само инвертибилне показиваче: за сваки показивач од чвора x до чвора y, инверзибилни показивач од y до x мора бити присутан. С обзиром да излазни показивачи морају бити обележени различитим симболима абецеде, оба КУМ и СММ графа имају О(1) излазни степен. Међутим, инверзибилност показивача КУМ ограничава улазни степен на О(1), такође. Додатна разлика је у томе што је КУМ замишљена као генерализација Турингове машине, тако да омогућава тренутно "активним" чворовима да се померају у оквиру графа. Сходно томе, чворови се могу одредити појединим карактерима уместо речима, а акције које треба предузети могу се одредити табелом стања уместо фиксираном листом инструкција.

Види још

• Регистарска машина
• Машина са случајним приступом
• Машина са случајним приступом ускладиштеног програма
• Турингова машина
• Пост турингова машина

Литература

• "Он Колмогоров Мацхинес Анд Релатед Иссуес", Yури Гуревицх
• Андреy Колмогоров анд V. Успенскии, Он тхе дефинитион оф ан алгоритхм,Успехи Мат. Наук. 13 (1958), 3-28. Енглисх транслатион ин Америцан Матхематицал Социетy Транслатионс, Сериес II, Волуме 29 . (1963). стр. 217–245.
• Ј. Е. Саваге (1998), Моделс оф Цомпутатион: Еxплоринг тхе Поwер оф Цомпутинг. Аддисон Wеслеy Лонгман.
• А. Сцхōнхаге (1970), Универселле Туринг Спеицхерунг, Аутоматентхеорие унд Формале Спрацхен, Дōрр, Хотз, едс. Библиогр. Институт, Маннхеим, (1970). стр. 69–383.