Maŝino de Turing

Arta prezento de la Maŝino de Turing
Model of a Turing machine
Modela efektivigo de maŝino de Turing, unu el multaj.

Maŝinoj de Turing estas ekstreme simplaj simbol-manipulantaj aparatoj, kiuj — malgraŭ sia simpleco — povas esti adaptitaj por simuli la logikon de ajna komputilo, kiu eble povus esti foje konstruata (kvankam eble tre malefike). Ili estis priskribitaj en 1936 fare de Alan Turing. Maŝino de Turing, kiu kapablas simuli ajnan alian maŝinon de Turing, estas nomata universala maŝino de Turing (aŭ simple universala maŝino).

Historio

En 1936, responde al la demando de Godelo pri tio, kio estas komputebla, Alan Turing verkis artikolon nomitan On Computable Numbers (Pri komputeblaj nombroj), en kiu li priskribis modelon de komputilo en formo plej simpla, abstrakta kaj esenca — tia modelo estas hodiaŭ konata kiel maŝino de Turing.

Priskribo

Maŝino de Turing konsistas el tri partoj:

  • Rubando, dividita en ĉelojn, por registri la demandon kaj respondon de la maŝino en la formo de vico da skribsignoj el finia alfabeto (en unu ĉelon eblas skribi unu signon).
  • Legilo/skribilo por legi kaj skribi la literojn. Ĝi kapablas legi literon, skribi literon, moviĝi laŭ la rubando je unu paŝo dekstren aŭ maldekstren.
  • Decidilo kiu prenas literon el la legilo kaj, depende de la litero, ordonas al la legilo moviĝi aŭ skribi aŭ legi.

Signifo

La tuto ŝajnas esti simpla, sed Turing pruvis, ke tia maŝino povas komputi ion ajn, kio estas komputebla. Fakte, ĉiu ekzistanta komputilo estas esence tia maŝino. La diversaj modernaj teĥnologioj, uzataj nun, estas nome nur rimedoj por plirapidigi aŭ pligrandskaligi la komputadon, do diferenco de grado, sed ne de speco nek de esenco nek de ebleco. Laŭ materialistoj (ekzemple Daniel Dennett), eĉ la homa cerbo estas maŝino de Turing.

Lambdokalkulo

Teorio pri tio, ke ĉiu komputebla funkcio povas esti komputata de Maŝino de Turing nomiĝas la Tezo Church-Turing. Al ĝia ekesto kontribuis Alonzo Church, alia matematikisto de tiu tempo. De li priesplorita lambdokalkulo estas ekvivalento de la Maŝino de Turing kaj oni povas pruvi, ke ankaŭ ĝi povas komputi ĉiujn komputeblajn funkciojn.

Vidu ankaŭ

Eksteraj ligiloj

Read other articles:

Robert B. Sherman

Halaman ini berisi artikel tentang penulis lagu dan naskah Amerika. Untuk tokoh lain bernama Robert Sherman, lihat Robert Sherman (disambiguasi). Robert B. ShermanSherman pada 2002LahirRobert Bernard Sherman(1925-12-19)19 Desember 1925New York, New York, ASMeninggal6 Maret 2012(2012-03-06) (umur 86)London, InggrisMakamHillside Memorial Park Cemetery, Culver City, CaliforniaKebangsaanAmerikaNama lainRobert ShermanBob ShermanBobMoosePekerjaanPenulis lagu, penulis naskah, penerbitTahun...

 

Papias dari Hierapolis

PapiasUskup Hierapolis, Bapa ApostolikMeninggalsetelah tahun 100Dihormati diGereja Katolik Roma, Gereja Katolik TimurPesta22 Februari[1] Papias (bahasa Yunani: Παπίας) adalah seorang Bapa Apostolik, Uskup Hierapolis (sekarang kota Pamukkale, Turki), dan pengarang (~ tahun 100) Eksposisi Perkataan-perkataan Tuhan (bahasa Inggris: Exposition of the Sayings of the Lord; bahasa Yunani: Λογίων Κυριακῶν Ἐξήγησις) dalam lima jilid. Karya ini, sekaran...

 

Susan Illston

American judge (born 1948) Susan Yvonne IllstonIllston in 2014Senior Judge of the United States District Court for the Northern District of CaliforniaIncumbentAssumed office July 1, 2013Judge of the United States District Court for the Northern District of CaliforniaIn officeMay 26, 1995 – July 1, 2013Appointed byBill ClintonPreceded byBarbara A. CaulfieldSucceeded byVince Chhabria Personal detailsBorn (1948-06-24) June 24, 1948 (age 75)Tokyo, JapanEducationDuke University...

Yoo Jae-suk

South Korean entertainer (born 1972) In this Korean name, the family name is Yoo. Yoo Jae-sukYoo in 2017Born (1972-08-14) 14 August 1972 (age 51)Seoul, South KoreaEducationSeoul Institute of the ArtsYears active1991–presentAgentAntennaSpouse Na Kyung-eun [ko] ​ ​(m. 2008)​Children2Comedy careerMediumStand-uptelevisionGenresObservationalsketchwitparodyslapstick Musical careerAlso known asYoo San-seulU-DoragonJimmy YooGenresTrotInstrum...

 

DUSP3

Proteína fosfatasa dual específica 3 Estructura tridimensional de la proteína DUSP3.Estructuras disponiblesPDB Buscar ortólogos: PDBe, RCSB  Lista de códigos PDB1j4x IdentificadoresSímbolos DUSP3 (HGNC: 3069) VHRIdentificadoresexternos OMIM: 600183 EBI: DUSP3GeneCards: Gen DUSP3UniProt: DUSP3Locus Cr. 17 q21.31               Ontología génica Referencias: AmiGO / QuickGO OrtólogosEspecies Humano Ratón Ent...

 

Tea Party Patriots

Right wing American political organization Tea Party PatriotsFormation2009Type501(c)(4) non-profitHeadquartersAtlanta, GeorgiaCo-foundersJenny Beth Martin and Mark MecklerWebsiteTeaPartyPatriots.org This article is part of a series onConservatismin the United States Schools Compassionate Fiscal Fusion Libertarian Moderate Movement Neo Paleo Progressive Social Traditionalist Principles American exceptionalism Anti-communism Christian nationalism Classical liberalism Constitutionalism Family va...

Boothtown Aqueduct

This article is about the water bridge. For the nature reserve which incorporates the aqueduct, see Lower Prospect Canal Reserve. BridgeBoothtown AqueductCoordinates33°49′51″S 150°56′18″E / 33.830950°S 150.938244°E / -33.830950; 150.938244CharacteristicsTotal lengthc. 225 m (738 ft)No. of spans22Capacity423 ML (14.9×10^6 cu ft) dailyHistoryConstruction startJanuary 1886Opened1888Closed1907Location The Boothtown Aqueduct is a herita...

 

Olivia (1951 film)

1951 French filmOliviaFrench theatrical release posterDirected byJacqueline AudryScreenplay byPierre LarocheColette Audry (adaptation)Based onOliviaby Dorothy BussyStarring Edwige Feuillère Simone Simon Marie-Claire Olivia CinematographyChristian MatrasMusic byPierre SancanProductioncompanyMemnon FilmsDistributed by Filmsonor (France) Arthur Davis Associates (USA) Release dates 27 April 1951 (1951-04-27) (France) 8 April 1954 (1954-04-08) (U.S.) Running ...

 

Gorgoroth discography

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: Gorgoroth discography – news · newspapers · books · scholar · JSTOR (June 2013) (Learn how and when to remove this template message) Gorgoroth discographyGorgoroth, live at Hole In The Sky 2009Studio albums9Live albums3Video albums1EPs2Other appearances8 Gorgor...

XIV Campionati mondiali di wushu

XIV Campionati mondiali di wushu Competizione Campionati mondiali di Wushu Sport Wushu Edizione 14ª Organizzatore Federazione Internazionale di Wushu Date dal 19 settembreal 3 ottobre 2017 Luogo Kazan' Impianto/i Centro di Ginnastica di Kazan' Statistiche Miglior nazione  Cina (15) Cronologia della competizione 2015 Giacarta 2019 Shanghai Manuale I XIV Campionati mondiali di Wushu (Inglese: 2017 World Wushu Championships) sono stati la 14ª edizione dei Campionati mondiali ...

 

Locations in New Zealand with a Scottish name

This is a list of placenames in Scotland which have subsequently been applied to parts of New Zealand by Scottish emigrants or explorers. Main article: Scottish place names in other countries The South Island also contains the Strath-Taieri and the Ben Ohau Range of mountains, both combining Scots Gaelic and Māori origins, as does Glentaki, in the lower valley of the Waitaki River. Invercargill has the appearance of a Scottish name, since it combines the Scottish prefix Inver (Inbhir), meani...

 

RTZ (radio station)

Time signal transmitter in Russia This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) The topic of this article may not meet Wikipedia's notability guidelines for products and services. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability...

Nirala Sweets

Defunct confectionery chain in Pakistan Nirala Sweets & CafeIndustryBakersFounded1948; 75 years ago (1948)FounderTaj DinDefunct2016; 7 years ago (2016)HeadquartersLahore, PakistanNumber of locations22 outlets in Pakistan, 2 in the UAEKey peopleTaj Din (founder owner of family business)Farooq Ahmed (son)Faisal Farooq and Ahmer Farooq (grandchildren and Managing Directors of business)ProductsSweets, snacks, dairy, beverages A Nirala Sweets outlet in Islam...

 

Frank Minis Johnson

American judge (1918–1999) For other people with the same name, see Frank Johnson (disambiguation). Frank JohnsonSenior Judge of the United States Court of Appeals for the Eleventh CircuitIn officeOctober 30, 1991 – July 23, 1999Judge of the United States Court of Appeals for the Eleventh CircuitIn officeOctober 1, 1981 – October 30, 1991Preceded bySeat establishedSucceeded byEdward Earl CarnesJudge of the United States Court of Appeals for the Fifth CircuitIn officeJu...

 

Old Aberdeen

This article is about Old Aberdeen. For other uses of Aberdeen, see Aberdeen (disambiguation). Human settlement in ScotlandOld AberdeenScottish Gaelic: Seann Obar DheathainScots: Auld AiberdeenArms of Old AberdeenOld AberdeenLocation within the Aberdeen City council areaShow map of AberdeenOld AberdeenLocation within ScotlandShow map of ScotlandOS grid referenceNJ939082Council areaAberdeen CityLieutenancy areaAberdeenCountryScotlandSovereign stateUnited KingdomPost to...

My Solo Project

2000 studio album by Mates of StateMy Solo ProjectStudio album by Mates of StateReleasedJune 15, 2000Recorded1999-2000GenreIndie pop, electronicaLabelOmnibus RecordsMates of State chronology My Solo Project(2000) Our Constant Concern(2002) Professional ratingsReview scoresSourceRatingAllMusic[1]Pitchfork Media(7.6/10)[2]Tiny Mix Tapes[3] My Solo Project is the debut album by Mates of State.[4][5] Track listing Names - 0:51 Proofs - 2:17 What I C...

 

Alpha Girl

For the marketing concept, see Influencer marketing. Alpha GirlCover of the first issuePublication informationPublisherImage ComicsScheduleMonthlyFormatOngoing seriesGenrePost-apocalyptic, Zombies in comicsPublication dateFebruary 2012 to presentNo. of issues5Main character(s)JudithCreative teamWritten byJean-Paul Bonjour, Jeff RoenningArtist(s)Robert Love, Dana Shukartsi, Diego Simone[1] Alpha Girl is an American five issue comic book series written by Jean-Paul Bonjour and Jeff Roen...

 

Valle de Ferganá

Valle de Ferganá Farg‘ona vodiysi - Фергана өрөөнү - водии Фaрғонa - Ферганская долина - وادی فرغانه Región histórica-geográfica de Asia central Localización geográficaContinente Asia CentralCoordenadas 40°54′03″N 71°45′28″E / 40.900833333333, 71.757777777778Localización administrativaPaís Kirguistán Kirguistán  TayikistánUzbekistán UzbekistánSubdivisión Ciudad de Osh y provincias de Batken, J...

San Carlos Apache Police Department

Tribal police agency This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may rely excessively on sources too closely associated with the subject, potentially preventing the article from being verifiable and neutral. Please help improve it by replacing them with more appropriate citations to reliable, independent, third-party sources. (May 2022) (Learn how and when to remove this ...

 

Wild Dances

2004 song by Ruslana This article is about the song. For the album, see Wild Dances (album). Wild DancesSingle by Ruslanafrom the album Wild Dances B-sideHutsul GirlReleased17 May 2004 (2004-05-17)Length3:00LabelEMISongwriter(s) Oleksandr Ksenofontov Jamie Maher Ruslana Lyzhychko Michael Fayne Sherena Dugani Producer(s) Oleksandr Ksenofontov Ruslana Lyzhychko Ruslana singles chronology Kolomyjka (2003) Wild Dances (2004) Dance with the Wolves (2005) Eurovision Song Contest 2004...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!