Машина Поста

Машина Поста (див.Еміль Пост) — це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. Машина Поста, хоча зовнішньо проста, може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення. Машиною ця математична конструкція названа тому, що при її побудові використовуються деякі поняття реальних машин (елемент пам'яті, команда тощо).

Машину Поста можна розглядати як спрощену модель комп'ютера. Насправді, як комп'ютер, так і машина Поста мають:

  • неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими;
  • обмежений набір елементарних дій — команд, кожна з яких виконується за один такт (крок).

Обидві машини працюють на основі програми. Проте у машині Поста інформація розташовується лінійно і читається підряд, а в комп'ютері можна читати інформацію за адресою; набір команд комп'ютера значно ширший і виразніший за команди машини Поста.

Склад машини Поста

Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру. Комірка стрічки може бути порожньою, або у ній може перебувати мітка V. Інформація про те, які комірки порожні, а які містять мітки, утворює стан стрічки. Іншими словами, стан стрічки — це розподіл міток по комірках. Стан стрічки змінюється у процесі роботи машини. Зауважимо, що наявність міток у комірці можна інтерпретувати як «1», а відсутність як «0». Таке двійкове представлення інформації подібне до уявлення, яке використовується практично у всіх сучасних комп'ютерах.

Каретка може пересуватися вздовж стрічки вліво і вправо. Коли вона нерухома — вона перебуває навпроти однієї комірки стрічки. У такому випадку говорять, що каретка оглядає одну комірку. За одиницю часу каретка може зробити одну із трьох дій: стерти мітку, поставити мітку, зробити рух до сусідньої комірки. Стан машини Поста складається із стану стрічки і розташування каретки. Дії каретки підпорядковані програмі, яка складається з пронумерованого набору команд (команди можна представляти як рядки програми). Команди бувають шести типів:

  1. записати 1 (мітку), перейти до i-го рядка програми;
  2. записати 0 (стерти мітку), перейти до i-го рядка програми;
  3. переміститися вліво, перейти до i-го рядка програми;
  4. переміститися вправо, перейти до i-го рядка програми;
  5. зупинитися;
  6. якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми.

Наведемо перелік неприпустимих дій, які ведуть до аварійної зупинки машини:

  • спроба записати 1 (мітку) в заповнену комірку;
  • спроба стерти мітку в порожній комірці;
  • нескінченне виконання (зациклення).

Програма Поста

Кожна програма машини Поста складається з команд. Кожна команда програми складається з номера команди, операції та переходу. Наприклад:

  • команда зміщення праворуч: i → j
  • команда зміщення ліворуч: i ← j
  • команда встановлення мітки: i j j
  • команда знищення мітки: i ε j
  • команда передачі керування: i ?→ j1, j2
  • команда зупинки: i стоп або і ! (знак оклику)

Відповідно, програма машини Поста — це скінчений перелік команд, що має наступні властивості:

  • на n-му місці записується команда з номером N;
  • передача керування повинна відбуватися тільки до існуючого номеру команди.

Необхідні умови роботи машини Поста

  • визначеність стану машини Поста (місцерозташування каретки і міток);
  • наявність програми машини Поста.

Зауваження щодо роботи машини Поста

  • виконання команди встановлення/знищення мітки не призводить до переміщення каретки і можливе тільки за умови пустої / відміченої комірки;
  • виконання команди передачі керування з верхнім та нижнім індексом не змінює стан машини Поста. Верхній перехід відбувається у випадку, коли комірка, яку визначає каретка, порожня, і навпаки.

Результат виконання програми машини Поста

  • під час виконання програми машина Поста зустрічає команду зупинки, що призводить до результативної зупинки.
  • під час виконання програми машина Поста зустрічає некоректну команду, що призводить до без результативної зупинки.
  • під час виконання програми машина Поста не зустрічає жодної з вищезазначених команд, що призводить до циклічного виконання.

Примітки

Різні програми, що обробляють однаковий початковий стан, можуть призводити до будь-якого з цих трьох результатів, і навпаки, одна і та ж програма може давати різні результати для різних початкових станів.

Графічне представлення команд машини Поста

n.   →   mКрок вправо
n.   ←   mКрок вліво
n.   V   mЗаписати мітку
n.   X   mСтерти мітку
n.   ? a: b  Переглянути комірку: якщо в комірці знаходиться 0, тоді перейти на команду з номером а, інакше на команду з номером b.
n.   !Зупинка

Будемо розуміти, що ми можемо застосувати програму до біжучого стану машини Поста, якщо виконання програми не призведе до зациклювання, тобто рано чи пізно ми виконаємо команду «Зупинка».

Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: n K m, де n — порядковий номер команди, K − дія, яка виконується кареткою, m — номер наступної команди, яку необхідно виконати.

З погляду властивостей алгоритмів, що вивчаються за допомогою машини Поста, найбільший інтерес представляють причини зупинки машини під час виконанні програми:

  • зупинка за командою «стоп». Така зупинка називається результативною і вказує на коректність алгоритму;
  • зупинка при виконанні неприпустимої команди. У цьому випадку зупинка називається безрезультатною;
  • машина не зупиняється ніколи. У цьому і у попередньому випадку ми маємо справу з некоректним алгоритмом.

Під початковим станом каретки розумітимемо її положення навпроти порожньої комірки лівіше за найлівішу мітку на стрічці.

Приклад 1

На стрічці в одній з комірок поставлена мітка (решта комірок є порожніми). Каретка стоїть на деякій відстані лівіше за цю комірку. Потрібно підвести каретку до комірки, стерти мітку і зупинити каретку зліва від цієї комірки.

Розв'язок. Спочатку спробуємо описати алгоритм звичайною мовою. Оскільки нам відомо, що каретка стоїть навпроти порожньої комірки, але невідомо, скільки кроків потрібно зробити до заповненої комірки, ми можемо відразу зробити крок вправо; перевірити, чи заповнена комірка; якщо вона порожня, то повторювати ці дії доти, поки не наштовхнемося на заповнену комірку. Щойно ми її знайдемо, ми виконаємо операцію стирання, після чого потрібно буде лише змістити каретку вліво і зупинити виконання програми. Програма пошуку і стирання єдиної мітки на стрічці для машини Поста має такий вигляд:

  1. → 2
  2. ? 1: 3
  3. X 4
  4. ← 5
  5. !

Приклад 2

На стрічці заданий масив міток. Збільшити довжину масиву на 2 мітки. Каретка знаходиться або зліва від масиву, або над однією з комірок масиву.

Розв'язок.

  1. ? 2: 3 (команди 1 і 2 — пересуваємо каретку до масиву)
  2. → 1
  3. → 4 (команди 3 і 4 — пересуваємо каретку до кінця масиву)
  4. ? 5: 3
  5. V 6 (команди 5–7 — ставимо 2 мітки в кінець масиву)
  6. → 7
  7. V 8
  8. ! (стоп)

Приклад 3

Задано два масиви міток, які знаходяться на деякій відстані один від одного. Потрібно об'єднати їх в один масив. Каретка знаходиться над крайньою лівою міткою першого масиву (в початковому стані).

  1. X 2
  2. → 3
  3. ? 4: 2
  4. V 5
  5. → 6
  6. ? 8; 7
  7. !
  8. ← 9
  9. ? 10: 8
  10. → 1

Див. також

Джерела

  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
  • Роджерс Х.(інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
  • С. М. Прийма «Теорія алгоритмів і математична логіка»
  • Навчальні матеріали з інформатики " Основні поняття інформатики " Машина Поста [Архівовано 29 травня 2014 у Wayback Machine.]

Read other articles:

Peta negara bagian di Nigeria Negara bagian adalah wilayah administratif tingkat satu di Nigeria. Lihat pula ISO 3166-2:NG Templat:Negara bagian di Nigeria Artikel bertopik Nigeria ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.lbs

 

العلاقات الغانية اللوكسمبورغية غانا لوكسمبورغ   غانا   لوكسمبورغ تعديل مصدري - تعديل   العلاقات الغانية اللوكسمبورغية هي العلاقات الثنائية التي تجمع بين غانا ولوكسمبورغ.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه ا...

 

For other ships with the same name, see USS Gallatin. USS Gallatin (APA-169) at anchor in San Francisco Bay, late 1945 or early '46 History United States NameUSS Gallatin Namesake Gallatin County, Illinois Gallatin County, Kentucky Gallatin County, Montana Orderedas type VC2-S-AP5 Laid down13 August 1944 Launched17 October 1944 Acquired15 November 1944 Commissioned15 November 1944 Decommissioned23 April 1946 Stricken8 May 1946 FateSold for scrapping in Spain, 17 September 1983 General charact...

Questa voce sull'argomento stagioni delle società calcistiche italiane è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Voce principale: Unione Sportiva Lecce. Associazione Calcistica LecceStagione 1938-1939Sport calcio Squadra Lecce Allenatore Giovanni Battista Rebuffo Presidente G. Giorgino Serie C - Gir. H4º posto (retrocesso al 12º e ultimo posto per delibera della Presidenza Federale a caus...

 

Fabiano Parisi Nazionalità  Italia Altezza 178 cm Peso 70 kg Calcio Ruolo Difensore Squadra  Fiorentina Carriera Giovanili 2011-2016 Pro Irpinia2016-2017 Vigor Perconti2017-2018 Benevento Squadre di club1 2018-2020 Avellino63 (4)[1]2020-2023 Empoli78 (3)2023- Fiorentina15 (0) Nazionale 2021-2023 Italia U-2111 (1) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo → indica un trasferimento in presti...

 

International channels of BET Networks Television channel BET InternationalCountryUnited KingdomBroadcast areaAfricaMiddle EastSouth KoreaFranceNetworkBETHeadquartersLondon, United KingdomProgrammingLanguage(s)EnglishArabicKoreanFrenchPicture format16:9 1080i HDTVOwnershipOwnerParamount International NetworksHistoryLaunched27 February 2008; 16 years ago (2008-02-27)1 December 2015; 8 years ago (2015-12-01) (South Africa)Closed8 April 2021; 3 ye...

Museum Tomok adalah museum yang memamerkan koleksi terkait dengan kehidupan masyarakat Toba di masa lampau[1]. Museum ini terletak di Desa Tomok, Kecamatan Simanindo, Kabupaten Samosir, Sumatera Utara. Di bangun pada tahun 2005, dengan arsitektur bangunan khas Batak yang disebut Rumah Bolon. [2] Museum Batak, Tomok (Tampak Depan) Karakteristik Selain berkawasan di sekitar Danau Toba, museum ini disorot karena bentuk bangunan yang mirip dengan Rumah Bolon sehingga mendapatkan n...

 

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています(詳細)。 数字の大字(だいじ)は、漢数字の一種。通常用いる単純な字形の漢数字(小字)の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券(「壱」が大字) 弐千円日本銀行券(「弐」が大字) 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

Halaman ini berisi artikel tentang tentang sebuah wilayah administratif tingkat dua jenis county di Negara Bagian Hawaii. Untuk sebuah teritori tergabung terselenggara Amerika Serikat, lihat Teritori Hawaii.Hawaii County, HawaiiW. H. Shipman House Seal of Hawaii County, HawaiiSealLokasi di negara bagian HawaiiLokasi negara bagian Hawaii di Amerika SerikatDidirikan1905Pemerintah• MayorHarry KimSeatHiloKota terbesarHiloWilayah • Keseluruhan508.670 sq mi (1.317.449&#...

Hungarian composer, conductor and teacher (1944–2024) The native form of this personal name is Eötvös Péter. This article uses Western name order when mentioning individuals. Péter EötvösEötvös in 2018Born(1944-01-02)2 January 1944Székelyudvarhely, Kingdom of HungaryDied24 March 2024(2024-03-24) (aged 80)Budapest, HungaryEducation Franz Liszt Academy of Music Musikhochschule Köln Occupations Composer Conductor Academic teacher Organizations Oeldorf Group Ensemble InterCon...

 

German theologian and minister; bishop of the Moravian Brethren August Gottlieb Spangenberg engraved by Johann Gotthard von Müller August Gottlieb Spangenberg (15 July 1704 – 18 September 1792) was a German theologian and minister, and a bishop of the Moravian Church. As successor of Count Nicolaus Zinzendorf, he helped develop international missions and stabilized the theology and organization of the German Moravian Church. Early life and education Spangenberg was born in Kle...

 

American Founding Father and politician (1734–1821) For other people named William Floyd, see William Floyd (disambiguation). William FloydMember of the U.S. House of Representativesfrom New York's 1st districtIn officeMarch 4, 1789 – March 3, 1791Preceded byNew districtSucceeded byThomas Tredwell Personal detailsBorn(1734-12-17)December 17, 1734Brookhaven, Province of New York, British AmericaDiedAugust 4, 1821(1821-08-04) (aged 86)Westernville, New York, U.S.Po...

赫尔穆特·科尔Helmut Kohl第6任德國聯邦总理任期1982年10月1日—1998年10月27日总统卡尔·卡斯滕斯里夏德·冯·魏茨泽克罗曼·赫尔佐克副职汉斯-迪特里希·根舍于尔根·穆勒曼(英语:Jürgen Möllemann)克劳斯·金克尔前任赫尔穆特·施密特继任格哈德·施罗德 德国基督教民主联盟领袖任期1973年6月12日—1998年11月7日前任赖纳·巴泽尔(英语:Rainer Barzel)继任沃尔夫冈·朔伊布勒 莱�...

 

Hizkia (Hizqiyyahu ben Ahaz)Raja Yehuda (Melekh Yehudah)BerkuasaPemerintahan bersama dengan Ahas 729, Memerintah sendiri716 – 697 SM bersama Manasye 697 - 687PendahuluRaja AhasPenerusManasyeKelahiran~739 SMmungkin YerusalemKematian~687 SMYerusalemWangsaKeturunan DaudAyahRaja AhasIbuAbi, juga disebut AbiaAnakManasye Hizkia (bahasa Ibrani: חִזְקִיָּ֫הוּ atau יְחִזְקִיָּ֫הוּ, bahasa Yunani: Ἐζεκίας, Ezekias, dalam Septuaginta; bahasa Latin: Ezechias; 739-687...

 

Women's fashion magazine InStyleCover of the March 2019 issue, featuring Brie LarsonEditor Sally HolmesCategoriesCelebrity, human interest, newsTotal circulation(2013)1,810,539 (US)[1]First issueJune 1994; 30 years ago (1994-06)Final issueMarch 2022; 2 years ago (2022-03) (print)CompanyDotdash MeredithCountryUnited StatesBased inNew York CityLanguageEnglishWebsiteinstyle.com (US)ISSN1076-0830 InStyle is an American monthly women's fashion ...

Horacio Cartes Presiden Paraguay ke-50Masa jabatan15 Agustus 2013 – 15 Agustus 2018Wakil PresidenJuan AfaraAlicia PuchetaPendahuluFederico FrancoPenggantiMario Abdo Benítez Informasi pribadiLahir5 Juli 1956 (umur 68)Asunción, ParaguayPartai politikPartai ColoradoSunting kotak info • L • B Horacio Manuel Cartes Jara (lahir 5 Juli 1956[1]) adalah pengusaha asal Paraguay dan Presiden paraguay terpilih pada pemilihan umum April 2013. Referensi ^ (Portugis) ...

 

English politician, landowner and planter For other people named Robert Davers, see Robert Davers (disambiguation). Sir Robert Davers, 2nd BaronetSir Robert Davers, 2nd Baronet by Jonathan Richardson, c.1700Bornc.1653BarbadosDied1 October 1722Rushbrooke Hall, Suffolk, EnglandFatherSir Robert Davers, 1st BaronetMotherEleanor LukeOccupationPolitician, landowner and slavetrader Sir Robert Davers, 2nd Baronet (c. 1653 – 1 October 1722) was an English Tory politician, landowner and planter.[...

 

Liegnitz ist eine Weiterleitung auf diesen Artikel. Siehe auch: Liegnitz (Begriffsklärung). Legnica Legnica (Polen) Legnica Basisdaten Staat: Polen Woiwodschaft: Niederschlesien Powiat: Kreisfreie Stadt Fläche: 56,30 km² Geographische Lage: 51° 12′ N, 16° 10′ O51.20833333333316.160277777778Koordinaten: 51° 12′ 30″ N, 16° 9′ 37″ O Höhe: 108 m n.p.m. Einwohner: 98.436 (31. Dez. 2020)[1] Postleitzahl: 59-220 Tele...

Dit artikel gaat over de film Angels & Demons, zie Het Bernini Mysterie voor het boek van deze film met meer informatie over het plot. Angels & Demons Tom Hanks en Ayelet Zurer buiten het Pantheon in Rome tijdens de productie. Tagline The holiest event of our time. Perfect for their return.The path is alive! Regie Ron Howard Producent Brian GrazerJohn Calley Scenario Dan Brown (boek)Akiva Goldsman (script) Gebaseerd op Het Bernini Mysterie van Dan Brown Hoofdrollen Tom HanksEwan McGr...

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (يوليو 2016) جزء من سلسلة مقالات حولديانة قدماء المصريين مفاهيم الحياة الآخرة دوات ماعت الأساطير الأرقام الفلسفة الرو...