Unambiguous Turing machine

Turing machines
Machine
Turing machine equivalents Turing machine examples
Variants
Alternating Turing machine Neural Turing machine Nondeterministic Turing machine Quantum Turing machine Post–Turing machine Probabilistic Turing machine Multitape Turing machine Multi-track Turing machine Symmetric Turing machine Total Turing machine Unambiguous Turing machine Universal Turing machine Zeno machine
Science
Alan Turing Category:Turing machine
v t e

In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments^{[by whom?]} to examine the abilities and limitations of computers.^{[citation needed]} An unambiguous Turing machine is a special kind of non-deterministic Turing machine, which, in some sense,^{[clarification needed]} is similar to a deterministic Turing machine.

Formal definition

A non-deterministic Turing machine is represented formally by a 6-tuple, $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ , as explained in the page non-deterministic Turing machine. An unambiguous Turing machine is a non-deterministic Turing machine such that, for every input $w=a_{1},a_{2},...,a_{n}$ , there exists at most one sequence of configurations $c_{0},c_{1},...,c_{m}$ with the following conditions:

$c_{0}$ is the initial configuration with input $w$
$c_{i+1}$ is a successor of $c_{i}$ and
$c_{m}$ is an accepting configuration.

In other words, if $w$ is accepted by $M$ , there is exactly one accepting computation.

Expressivity

The language of an unambiguous Turing machine is defined to be the same language that is accepted by the nondeterministic Turing machine. A language of strings L can be defined to be unambiguously recognizable if it is recognizable by an unambiguous Turing machine. The class of unambiguously recognizable languages is exactly the same as the class of recursively enumerable languages (RE).^{[citation needed]}

In particular, every deterministic Turing machine is an unambiguous Turing machine, as for each input, there is exactly one computation possible. Therefore, all recursively enumerable languages are unambiguously recognizable.

On the other hand, unambiguous non-deterministic polynomial time is suspected to be strictly less expressive than (potentially ambiguous) non-deterministic polynomial time.

References

Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3), 634–653

Read other articles:

List of SANFL premiers

This page is a chronological listing of the premiership winners in the South Australian National Football League (SANFL) – the premier Australian rules football competition in the state of South Australia. Chronological list Premiership decided by a Grand Final Premiership decided by a Grand Final Replay, after the scheduled Grand Final was drawn Premiership decided by a Challenge Final Premiership decided without any form of Grand Final Year...

Progress 26

Progress 26A Progress 7K-TG spacecraftMission typeMir resupplyCOSPAR ID1986-032A SATCAT no.16687[1] Spacecraft propertiesSpacecraftProgress (No.136)Spacecraft typeProgress 7K-TG[2]ManufacturerNPO Energia Start of missionLaunch date23 April 1986, 19:40:05 UTC[1]RocketSoyuz-U2[2]Launch siteBaikonur, Site 1/5 End of missionDisposalDeorbitedDecay date23 June 1986, 18:41:01 UTC[3] Orbital parametersReference systemGeocentricRegimeLow EarthPerigee altit...

Hans-Jürgen Kreische

Hans-Jürgen Kreische Nazionalità Germania Est Germania (dal 1990) Altezza 185 cm Peso 73 kg Calcio Ruolo Allenatore (ex attaccante) Termine carriera 1978 - giocatore 2001 - allenatore Carriera Squadre di club1 1964-1978 Dinamo Dresda256 (143) Nazionale 1968-1975 Germania Est46 (22)[1] Carriera da allenatore 1995-1996 Dinamo Dresda2000-2001 Dresdner SC Palmarès Olimpiadi Bronzo Monaco di Baviera 1972 1 I due numeri indicano le presenze e le reti segn...

Cycling at the 2015 European Games

Cycling contest at 2015 European Games Cycling at the 2015 European GamesVenueBMX Velopark (BMX)MTB Velopark (mountain biking)Dates16–27 JuneCompetitors346[1]2019 → Cycling at the2015 European GamesRoad cyclingRoad racemenwomenTime trialmenwomenMountain bikingCross countrymenwomenBMXBMXmenwomenvte Three disciplines of cycling were contested at the 2015 European Games: road cycling, mountain biking, and bicycle motocross (BMX). A total of eight medal events were held....

Kanzen

KanzenNama dagangKanzenSebelumnyaPT Semesta Citra MotorindoJenisSwastaIndustriOtomotifDidirikan2000Ditutup2010KantorpusatJakarta, IndonesiaProduksepeda motorSitus webwww.kanzenmotor.com Kanzen adalah merek sepeda motor Indonesia. Merek ini diproduksi oleh PT Semesta Citra Motorindo yang sebagian sahamnya dimiliki oleh mantan Menteri Perindustrian dan Menteri BUMN Rini Mariani Soemarno. Sepeda motor Kanzen menghasilkan beberapa jenis sepeda motor, di antaranya: Kanzen Scudetto, skuter otomatis...

Charity Shield FA 1985

Charity Shield FA 1985TurnamenCharity Shield FA Everton Manchester United 2 0 Tanggal10 Agustus 1985StadionStadion Wembley, London← 1984 1986 → Charity Shield FA 1985 adalah pertandingan sepak bola antara Everton dan Manchester United yang diselenggarakan pada 10 Agustus 1985 di Stadion Wembley, London. Pertandingan ini merupakan pertandingan ke-63 dari penyelenggaraan Charity Shield FA. Pertandingan ini dimenangkan oleh Everton dengan skor 2–0.[1] Pertandingan Everton v...

Spotify

Spotify Ltd.URLwww.spotify.comTipelayanan streaming musik, podcast directory, Program komputer, aplikasi seluler, komunitas daring dan pemerekan RegistrationDiperlukanSubjek utamalayanan daring, musik dan Industri musik Langue70 bahasaPenggunaGratis: 190 jutaPremium: 155 jutaTotal: 345 juta (4 Januari 2021[update])Bahasa pemrogramanPython, C++, JavaPembuatDaniel Ek dan Martin Lorentzon Web DeveloperSpotify Service entry7 Oktober 2008; 15 tahun lalu (2008-10-07)Tempat pembentukanS...

Koloni

Kolonisasi dan imperialisme pada akhir Perang Dunia II (1945) Koloni atau tanah jajahan adalah tempat yang dikuasai oleh negara lain. Negara metropolitan adalah negara yang memiliki koloni. Negara yang memiliki banyak koloni sering disebut sebagai Kerajaan. Penjajah adalah orang yang datang ke daerah asing untuk membuat koloni di sana dan kemudian mengontrol daerah itu. Kolonis adalah orang yang tinggal di koloni. Sekarang tidak lagi ada banyak negara yang de jure bersifat kolonial karena ber...

Flickr

FlickrURLFlickr.comTipeFoto Video Jejaring foto dan videoPerdagangan ?YaLangueInggris Cina Prancis Jerman Italia Portugis Bahasa Spanyol Korea IndonesiaBagian dariSmugMug PemilikYahoo! Inc.PembuatLudicorpWeb DeveloperSmugMug, Ludicorp dan Yahoo! (perusahaan) Service entryFebruari 2004Tempat pembentukanVancouver Lokasi kantor pusatSan Francisco Peringkat Alexa 30[1] KeadaanAktifBlog resmihttps://blog.flickr.net Flickr adalah situs web untuk berbagi foto dan situs komunitas daring ...

Lućmierz-Las

Village in Łódź Voivodeship, PolandLućmierz-LasVillageMemorial to World War II victimsLućmierz-LasCoordinates: 51°53′37″N 19°22′6″E / 51.89361°N 19.36833°E / 51.89361; 19.36833Country PolandVoivodeshipŁódźCountyZgierzGminaZgierzPopulation20 Lućmierz-Las (pronounced [ˈlut͡ɕmjɛʂ ˈlas], Lućmierz Forest) is a village in the administrative district of Gmina Zgierz, within Zgierz County, Łódź Voivodeship, in central Poland. It lies...

Janna

For other uses, see Janna (disambiguation). For the given name, see Jana (given name). Not to be confused with Jannah, meaning an eternal place, the Islamic conception of paradise. 13th century Kannada poet JannaOld Kannada poetic inscription (1196 AD) composed by Janna in the Amrutesvara temple at Amruthapura Janna (Kannada : ಮಹಾಕವಿ ಜನ್ನ) was one of the well-known Kannada poets of the early 13th century who also served in the capacity of a minister and a builder of t...

Stasiun Kakinoki

Stasiun Kakinoki柿ノ木駅Stasiun tersebut pada Mei 2005LokasiAnazawa, Uonuma-shi, Niigata-ken 946-0304JepangOperator■ JR EastJalur■ Jalur TadamiLetak112.4 km dari Aizu-WakamatsuJumlah peron1 peron sampingJumlah jalur1Informasi lainStatusDitutupSejarahDibuka01 Maret 1951 (1951-03-01)Ditutup14 Maret 2015 (2015-03-14)Sunting kotak info • L • BBantuan penggunaan templat ini Stasiun Kakinoki (柿ノ木駅code: ja is deprecated , Kakinoki-eki) adalah sebuah stasiun ke...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

Kemsing railway station

Railway station in Kent, England KemsingGeneral informationLocationKemsing, SevenoaksEnglandGrid referenceTQ567577Managed bySoutheasternPlatforms2Other informationStation codeKMSClassificationDfT category F2HistoryOpened1 June 1874Original companyLondon, Chatham and Dover RailwayPre-groupingSouth Eastern and Chatham RailwayPost-groupingSouthern RailwayPassengers2018/19 22,4762019/20 19,2762020/21 3,1222021/22 9,4782022/23 12,150 NotesPassenger statistics from the Office of Rail and Road Kemsi...

Remya Nambeesan

RamyaRamya NambeesanLahirRamya Subramaniam Unni1 Januari 1986 (umur 38)[1]Chottanikkara (Kochi), Kerala, India[2]Tempat tinggalValasaravakkam, Chennai, Tamil Nadu[1]KebangsaanIndiaAlmamaterSt. Teresa's College, ErnakulamPekerjaan Aktris film Penyanyi playback Presenter televisi Penari Tahun aktif2000–sekarangOrang tuaSubrahmaniam Unni JayasreeKerabatRahul Subrahmaniam (saudara) Ramya Nambeesan (juga disebut: Ramya Nambeesan) adalah seorang pemeran film dan...

Hannibal Hamlin

Hannibal Hamlin Hannibal Hamlin (27 Agustus 1809 – 4 Juli 1891) merupakan Wakil Presiden Amerika Serikat yang ke-15. Ia bersekolah di dekat rumahnya dan Akademi Hebron, lalu mengelola pertanian milik ayahnya. Pada beberapa tahun berikutnya, ia bekerja di beberapa bidang: kepala sekolah, koki, tukang kayu, surveyor, manajer di perusahaan surat kabar di Paris dan penyusun huruf di perusahaan percetakan. Ia belajar di fakultas hukum dan menjadi pengacara pada 1833. Lalu ia mulai ...

2008 San Diego Chargers season

NFL team 49th season 2008 San Diego Chargers seasonOwnerAlex SpanosGeneral managerA. J. SmithHead coachNorv TurnerHome fieldQualcomm StadiumResultsRecord8–8Division place1st AFC WestPlayoff finishWon Wild Card Playoffs(vs. Colts) 23–17 (OT)Lost Divisional Playoffs(at Steelers) 24–35Pro Bowlers 2[1] G Kris DielmanTE Antonio Gates AP All-Pros 1[2] G Kris Dielman (2nd team) ← 2007 Chargers seasons 2009 → A dramatic conclusion in week 10: Clinton H...

List of Gulag camps

The list below, enumerates the selected sites of the Soviet forced labor camps of the Gulag, known in Russian as the corrective labor camps, abbreviation: ITL. Most of them served mining, construction, and timber works. It is estimated that for most of its existence, the Gulag system consisted of over 30,000 camps, divided into three categories according to the number of prisoners held. The largest camps consisted of more than 25,000 prisoners each, medium size camps held from 5,000 to 25,00...

Kincardine and Mearns

57°02′06″N 2°18′25″W / 57.035°N 2.307°W / 57.035; -2.307 Map of Scotland showing the present-day committee area of Kincardine and Mearns Kincardine and Mearns is one of six area committees of the Aberdeenshire council area in Scotland. It has a population of 38,506 (2001 Census). There are significant natural features in this district including rivers, forests, mountains and bogs (known locally as mosses). Transport links with Aberdeen have encouraged rapid...

Framheim

Antarctic baseFramheim StationAntarctic baseFramheim in January 1911 (by Andreas Bloch)Framheim StationLocation of Framheim Station in AntarcticaCoordinates: 78°30′S 164°00′W / 78.5°S 164.0°W / -78.5; -164.0Country NorwayLocation in AntarcticaBay of WhalesRoss Ice ShelfEstablishedJanuary 1911 (1911-01)ClosedFebruary 1912 (1912-02) Framheim was the name of explorer Roald Amundsen's base at the Bay of Whales on the Ross Ice Shelf in Antar...

/profillengkap.com/index.php/article/1922–23 Torquay United F.C. season

Hirokazu Matsuno

Daftar antropolog Indonesia

Imbodu, Randangan, Pohuwato

Chrysoprasis valida

Kutamandiri, Tanjungsari, Sumedang

Pelican Lake First Nation

Pinworm infection