Машина Зенона

В математике и информатике Машина Зенона (иногда сокращаемая до ЗМ, также называемая ускоренной машиной Тьюринга) — это гипотетическая компьютерная модель, связанная с машиной Тьюринга, которая способна совершить счётное количество алгоритмических шагов за конечное время. В большинстве моделей вычислений такие машины не рассматриваются.

Более строго, машиной Зенона называется такая машина Тьюринга, которой требуется 2−n единиц времени для совершения n-го шага. Таким образом, первый шаг требует 0,5 единицы времени, второй — 0,25, третий — 0,125 и так далее, так что за единицу времени совершается бесконечное количество шагов.

Идея машины Зенона впервые обсуждалась Германом Вейлем в 1927 году. Своё название она получила в честь апорий древнегреческого философа Зенона Элейского. Такие машины играют ключевую роль в некоторых теориях. К примеру, теория точки Омега, разработанная Франком Типплером, верна, только если машина Зенона может существовать.

Машина Зенона и вычислимость

Некоторые функции, которые не могут быть вычислены на машине Тьюринга, могут быть вычислены с использованием машины Зенона. Например, на ней может быть решена проблема остановки (что иллюстрируется следующим псевдокодом): 

начало программы 
  записать 0 в первую ячейку на ленте;
  начало цикла
    смоделировать очередной шаг работы данной машины Тьюринга на данном входе;
    если машина Тьюринга остановилась, то записать 1 в первую ячейку на ленте и прервать цикл;
  конец цикла
конец программы

Такие вычисления, выходящие за рамки возможности машины Тьюринга, называются гипервычислениями.

Стоит заметить, что проблема остановки для самой машины Зенона не может быть решена на машине Зенона (Potgieter, 2006).

См. также

Ссылки

Read other articles:

The Prayer (film)

2018 film The PrayerFilm posterDirected byCédric KahnWritten byCédric KahnStarringAnthony BajonRelease dates 18 February 2018 (2018-02-18) (Berlin) 21 March 2018 (2018-03-21) (France) Running time107 minutesCountryFranceLanguageFrench The Prayer (French: La prière) is a 2018 French drama film directed by Cédric Kahn. It was selected to compete for the Golden Bear in the main competition section at the 68th Berlin International Film Festival.[1]...

 

 

The (Cyrillic)

Cyrillic letter used in three languages Not to be confused with the Latin letter Ç. Cyrillic letter Cyrillic letter Es with DescenderPhonetic usage:[θ], [ɕ]The Cyrillic scriptSlavic lettersАА̀А̂А̄ӒБВГҐДЂЃЕЀЕ̄Е̂ЁЄЖЗЗ́ЅИІЇꙆЍИ̂ӢЙЈКЛЉМНЊОО̀О̂ŌӦПРСС́ТЋЌУУ̀У̂ӮЎӰФХЦЧЏШЩꙎЪЪ̀ЫЬѢЭЮЮ̀ЯЯ̀Non-Slavic lettersӐА̊А̃Ӓ̄ӔӘӘ́Ә̃ӚВ̌ԜГ̑Г̇Г̣Г̌Г̂Г̆Г̈ҔҒӺҒ̌ӶД́Д̌Д̈Д̣Д̆ӖЕ̃Ё̄Є̈...

 

 

Pergola

PergolaPergola adalah bagian dari bangunan rumah atau berdiri sendiri sebagai peneduh atau pelindung dari panas dan terik sinar matahari. Fungsi Pergola berfungsi sebagai peneduh panas sinar matahari dengan cara memberikan bayangan yang teduh di bawahnya. Pergola biasa digunakan untuk meneduhkan area berjalan atau area duduk di luar ruangan. Struktur Pergola Bagian Atap Atap pergola berbentuk kisi-kisi tersusun sejajar berselang-seling. Pergola dilengkapi dengan tanaman rambat untuk memberi n...

Chester W. Wright

American economic historian Chester W. WrightChester W. Wright, 1911Born1879Died1966 (aged 86–87)NationalityAmericanAcademic careerInstitutionUniversity of ChicagoAlma materHarvard UniversityDoctoraladvisorFrank TaussigDoctoralstudentsHarold Innis Chester Whitney Wright (1879–1966) was an American economic historian, and Professor at the University of Chicago, known for his works on the economic history of the United States.[1][2] Biography Wright studied at ...

 

 

Barkat Gourad Hamadou

Barakat Gourad Hamadouبركات غوراد حمادو Perdana Menteri JibutiMasa jabatan2 Oktober 1978 – 7 Maret 2001PresidenHassan Gouled AptidonIsmaïl Omar Guelleh PendahuluAbdallah Mohamed KamilPenggantiDileita Mohamed Dileita Informasi pribadiLahir(1930-01-01)1 Januari 1930Tew'o, Somaliland Prancis (sekarang Jibuti)Meninggal18 Maret 2018(2018-03-18) (umur 88)Paris, PrancisSunting kotak info • L • B Barkat Gourad Hamadou (1 Januari 1930 – 18 ...

 

 

Eliezer Kaplan

Eliezer KaplanLahir27 Januari 1891Tempat lahirMinsk, Kekaisaran RusiaTahun aliyah1920Meninggal dunia13 Juli 1952(1952-07-13) (umur 61)Tempat meninggalTel Aviv, IsraelKnesset1, 2Faksi yang diwakili di Knesset1949–1952MapaiJabatan menteri1948–1952Menteri Keuangan1949–1950Menteri Perdagangan & Industri1952Wakil Perdana Menteri Eliezer Kaplan (Ibrani: אליעזר קפלן; bahasa Belarus: Эліэзер Каплан; 27 Januari 1891 – 13 Juli 1952) adalah s...

Alexis Raynaud

Cet article est une ébauche concernant le tir et un sportif français. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir Raynaud. Alexis RaynaudPierre Edmond Piasecki, Alexis Raynaud et Jérémy Monnier, de gauche à droite.BiographieNaissance 19 août 1994 (29 ans)GrasseNationalité françaiseFormation Université de StrasbourgActivité Tireur sportifAutres informationsTail...

 

 

The Last Warning

The Last WarningOriginal poster art featuring Laura La PlanteSutradaraPaul LeniProduserCarl LaemmleSkenario Alfred A. Cohn J.G. Hawks Robert F. Hill Tom Reed BerdasarkanThe Last Warningoleh Thomas F. FallonPemeran Laura La Plante Montagu Love Margaret Livingston John Boles Penata musikJoseph CherniavskySinematograferHal MohrPenyuntingRobert CarlisleDistributorUniversal PicturesTanggal rilis 25 Desember 1928 (1928-12-25) Durasi87 menit[1]NegaraAmerika SerikatBahasaInggris Th...

 

 

Ariel (moon)

Fourth-largest moon of Uranus ArielAriel in greyscale as imaged by Voyager 2 in 1986. Extensive grabens are visible, including the Kachina Chasmata in the upper part of the image.DiscoveryDiscovered byWilliam LassellDiscovery date24 October 1851DesignationsDesignationUranus IPronunciation/ˈɛəriəl/ or /ˈæriəl/[1]AdjectivesArielian /æriˈiːliən/[2]Orbital characteristics[3]Semi-major axis190900 kmEccentricity0.0012Orbital period (sidereal)2.520&#...

Malacca Sultanate

State on the Malay Peninsula and surrounding regions (1400–1511) Sultanate of Malaccaکسلطانن ملاک‎Kesultanan Melakac. 1400–1511The extent of the Sultanate in the 15th century, during the reign of Mansur Shah. Pre-modern Southeast Asian political borders are subject to speculation.CapitalMalacca (1400—1511)Bintan (1511—1526)Kampar (1526—1528)Common languagesClassical MalayReligion Sunni IslamDemonym(s)MalaccanGovernmentAbsolute monarchySultan • ...

 

 

تي في-أوت

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

 

 

Neobatrachia

Neobatrachia Обыкновенная квакша Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКласс:ЗемноводныеПодкласс:Б...

2005 en combiné nordique

Chronologies Chronologie du sport 2002 2003 2004  2005  2006 2007 2008Mois :Jan - Fév - Mar - Avr - Mai - Juin Juil - Aoû - Sep - Oct - Nov - Déc 2004 ◄◄ 2005 en sport ►► 2006 Chronologie dans le monde 2002 2003 2004  2005  2006 2007 2008Décennies :1970 1980 1990  2000  2010 2020 2030Siècles :XIXe XXe  XXIe  XXIIe XXIIIeMillénaires :Ier IIe  IIIe  Chronologies géographiques Afrique Afrique du Sud, Algérie, ...

 

 

Osteopathic medicine in the United States

Branch of the medical profession For the restricted-scope form of alternative medicine practice, mostly outside of North America, see Osteopathy. Further information: Comparison of MD and DO in the United States Osteopathic medicine in the United States Andrew Taylor Still (founder) Doctor of Osteopathic Medicine (DO) Medicine US Medical education Schools Physicians Osteopathic Manipulative Medicine AOA AACOM AAO COMLEX MD & DO Comparison Specialty Colleges AOA BOS vte Osteopathic medicin...

 

 

ASLwrite

Transcription system for American Sign Language ASLwriteYes? in ASLScript type Alternative (Iconic featural)CreatorAdrean Clark, Julia DameronCreated2011LanguagesAmerican Sign LanguageRelated scriptsParent systemsSignWritingsi5sASLwriteUnicodeUnicode rangeNot in UnicodeVery few ASL speakers use this writing system.ASLwrite's Website Stop sign mock-up in English (top) and ASL (bottom) ASLwrite (ASL: ) is a writing system that developed from si5s.[1] It was created to be an open-source,...

2022年羅德島州州長選舉

2022年羅德島州州長選舉 ← 2018 2022年11月8日 2026 →   获提名人 丹·麥基 阿什利·卡盧斯 政党 民主党 共和黨 民選得票 207166 139001 得票率 57.9% 38.9% 縣結果 直轄範市結果麥基:     40–50%     50–60%     60–70%     70–80%卡盧斯:     40–50%     50–60% 选前州長 丹·麥基 民主党 當...

 

 

Michelle Claire Edwards

South African badminton player (born 1974) Badminton playerMichelle Claire EdwardsPersonal informationCountrySouth AfricaBorn (1974-07-11) 11 July 1974 (age 50)Durban, KwaZulu-Natal, South AfricaHeight1.55 m (5 ft 1 in)Weight58 kg (128 lb)Women's singles & doublesHighest ranking300 (WS 26 August 2010)40 (WD 22 March 2012)51 (XD 14 July 2011) Medal record Women's badminton Representing  South Africa All-Africa Games 2003 Abuja Women's doubles 2003 Abuja M...

 

 

Лапачо

Сухой лапачо Лапачо (тахибо) — фиточай из коры муравьиного дерева, которое растёт в тропических джунглях Аргентины, Мексики и Перу. Светло-коричневый освежающий напиток со своеобразным горьковатым вкусом. Из того же дерева получают ценную древесину ипе, идущую на изг...

Dietro la porta chiusa

Dietro la porta chiusaUna scena del film.Titolo originaleSecret Beyond the Door... Lingua originaleinglese Paese di produzioneStati Uniti d'America Anno1948 Durata99 min Dati tecniciB/Nrapporto: 1,37:1 Generethriller, noir RegiaFritz Lang SoggettoRufus King SceneggiaturaSilvia Richards ProduttoreFritz Lang Produttore esecutivoWalter Wanger Casa di produzioneDiana Production Company Distribuzione in italianoUniversal Pictures FotografiaStanley Cortez MontaggioArthur Hilton MusicheMiklós R...

 

 

Thirty-fourth government of Israel

2015–20 government led by Benjamin Netanyahu This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Thirty-fourth government of Israel – news · newspapers · books · scholar...