RE (complexidade)

 Nota: Não confundir com Conjuntos recursivamente enumeráveis.

Em Teoria da Computabilidade e na Teoria da Complexidade Computacional, RE (recursivamente enumerável) é uma classe de problemas de decisão onde uma resposta "sim" pode ser verificada por uma máquina de Turing em uma quantidade finita de tempo.[1] Informalmente, isto significa que se a resposta é "sim", então existe algum procedimento que leva um tempo finito para determinar isso. Por outro lado, se a resposta é "não", a máquina poderá nunca parar. Equivalentemente, RE é uma classe de problemas de decisão para que uma máquina de Turing pode listar todas as instâncias "sim", uma por uma (isto é o que 'enumerável' significa).

Similarmente, co-RE é o conjunto de todas as linguagens que são complementos de uma linguagem em RE. De certo modo, co-RE contém linguagens em que a pertinência pode ser refutada em uma quantidade finita de tempo, mas provar a pertinência poderá levar uma eternidade.

Cada membro de RE é um recursivamente enumerável e, portanto, um conjunto diofantino.

Relações com outras classes

O conjunto das linguagens recursivas (R) é um subconjunto de ambas RE e co-RE.[2] De fato, é a intersecção dessas duas classes:

RE-completo

RE-completo é um conjunto de problemas de decisão que são completos para RE. De certo modo, estes são os mais "difíceis" problemas recursivamente enumeráveis. Todos esses problemas são não recursivos. Geralmente, nenhuma restrição é colocada sobre as reduções usadas exceto que elas sejam reduções por mapeamento.

Exemplos de problemas RE-completo:

  1. Problema da parada: Determinar se um programa para a partir de uma dada entrada ou se ele continuará rodando para sempre.
  2. Pelo Teorema de Rice, decidir a pertinência em qualquer subconjunto não-trivial do conjunto de funções recursivas é RE-hard. Isto será completo quando o conjunto for recursivamente enumerável.
  3. John Myhill (1955)[3] provou que todos os conjuntos criativos e produtivos são RE-completo.
  4. A uniformidade do problema da palavra para grupos ou semigrupos. [Na verdade, o problema da palavra para alguns grupos individuais é RE-completo.]
  5. Decidir a pertinência em uma gramática formal irrestrita geral. [Novamente,algumas gramáticas individuais têm problema de pertinência RE-completo.]
  6. O problema de validade para a lógica de primeira ordem.
  7. Problema da correspondência de Post: Dado um conjunto finito de palavras, determinas se existe uma palavra que pode ser formada em uma composição de palavras (permitindo repetição) em dois diferentes modos.
  8. Determinar se uma equação diofantina tem alguma solução inteira.

co-RE-completo

co-RE-completo é um conjunto de problemas de decisão que são completos para co-RE. De certo modo, estes são os complementos dos mais difíceis problemas recursivamente enumeráveis.

Exemplos de problemas co-RE-completo:

  1. O problema do dominó para o dominó de Wang.
  2. O problema da satisfabilidade para lógica de primeira ordem.

Ver também

Referências

  1. ↑ Predefinição:CZoo
  2. ↑ Predefinição:CZoo
  3. ↑ Myhill, John (1955), «Creative sets», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1: 97–108, MR 0071379, doi:10.1002/malq.19550010205 .
Ícone de esboço Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.

Read other articles:

Vehicle Assembly Building

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

Miss Universe 2010

Miss Universe 2010Ximena Navarrete, Miss Universe 2010TanggalAugust 23, 2010TempatMandalay Bay Events Center, Las Vegas metropolitan areaPembawa acaraBret Michaels, Natalie MoralesPengisi acaraJohn Legend & The Roots and Cirque du SoleilPenyiaranNBC, TelemundoPeserta83Finalis/Semifinalis15Tidak tampilBulgaria, Kepulauan Cayman, Estonia, Etiopia, Islandia, Montenegro, Namibia, VietnamTampil kembaliBotswana, Kepulauan Virgin Britania Raya, Denmark, Haiti, Kazakhstan, Sri...

 

List of acts of the Parliament of the United Kingdom from 2003

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

American College of Surgeons

Educational association of surgeons American College of SurgeonsAbbreviationACSFormation1913; 111 years ago (1913)[1]TypeProfessional associationHeadquartersChicago, Illinois, U.S.LocationUnited StatesMembership (2023) 88,000[2]Official language EnglishPresident, Board of RegentsE. Christopher Ellison, MD, FACS[3]Chair, Board of RegentsTimothy J. Eberlein, MD, FACS[3]Executive DirectorPatricia L. Turner[4]Websitewww.facs.org The Americ...

 

Risk aversion

Economics theory For the related psychological concept, see Risk aversion (psychology). Risk aversion (red) contrasted to risk neutrality (yellow) and risk loving (orange) in different settings. Left graph: A risk averse utility function is concave (from below), while a risk loving utility function is convex. Middle graph: In standard deviation-expected value space, risk averse indifference curves are upward sloped. Right graph: With fixed probabilities of two alternative states 1 and 2, risk...

 

SNOMED CT

System for medical classification This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (September 2022) (Learn how and when to remove this template message) SNOMED CTScreenshot of a SNOMED browserDeveloper(s)SNOMED InternationalTypemedical termsWebsitewww.snomed.orgAs of2007 SNOMED CT or SNOMED Clinical Terms is a systematically organized computer-processable collection of med...

Pakistan at the 2006 Asian Games

Sporting event delegationPakistan at the2006 Asian GamesIOC codePAKNOCPakistan Olympic Associationin DohaCompetitors387MedalsRanked 31st Gold 0 Silver 1 Bronze 3 Total 4 Asian Games appearances (overview)195419581962196619701974197819821986199019941998200220062010201420182022 Pakistan competed in the 2006 Asian Games held in Doha, Qatar. Medalists [1] Medal Name Sport Event Date  Silver Muhammad AkramNasir AliBadshah GulWajid AliWaseem SajjadMuhammad ArshadMaqsood AliRahat Maqsoo...

 

Actinide chemistry

Branch of nuclear chemistry Plutonium is a transuranic radioactive chemical element, an actinide metal. Actinide chemistry (or actinoid chemistry) is one of the main branches of nuclear chemistry that investigates the processes and molecular systems of the actinides. The actinides derive their name from the group 3 element actinium. The informal chemical symbol An is used in general discussions of actinide chemistry to refer to any actinide. All but one of the actinides are f-block elements, ...

 

Astronauta

Disambiguazione – Cosmonauta rimanda qui. Se stai cercando il film, vedi Cosmonauta (film). Disambiguazione – Astronauti rimanda qui. Se stai cercando il singolo di Margherita Vicario, vedi Astronauti (singolo). L'astronauta Bruce McCandless dello Space Shuttle. Fonte: NASA Un astronauta o cosmonauta[1] (in russo: космонавт, kosmonavt; in cinese: taikonauta[2]) è un essere umano che viaggia nello spazio o che viene trasportato da qualcosa che lo ...

95th National Guard Higher Command (Greece)

This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: 95th National Guard Higher Command Greece – news · newspapers · books · scholar · JSTOR (February 2013) (Learn how and when to remove this message) 95th National Guard Higher Command DIAGORIDON95η Ανώτερη Διοίκηση Ταγμάτων Εθνοφυλακής ΔΙ...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

 

國民陣線

国民阵线Barisan NasionalNational Frontباريسن ناسيونلபாரிசான் நேசனல்国民阵线标志简称国阵，BN主席阿末扎希总秘书赞比里署理主席莫哈末哈山总财政希山慕丁副主席魏家祥维纳斯瓦兰佐瑟古律创始人阿都拉萨成立1973年1月1日 (1973-01-01)[1]设立1974年7月1日 (1974-07-01)前身 联盟总部 马来西亚  吉隆坡 50480 秋傑区敦依斯迈路太子世贸中心（英�...

Узбекистон темир йуллари

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (27 июня 2016) Узбекистанские железные дорогиузб. O�...

 

Rock in a Hard Place

1982 studio album by AerosmithRock in a Hard PlaceStudio album by AerosmithReleasedAugust 27, 1982[1]Recorded1981–1982Studio Power Station, New York City Criteria, Miami GenreHard rockLength40:16LabelColumbiaProducer Jack Douglas Steven Tyler Tony Bongiovi Aerosmith chronology Night in the Ruts(1979) Rock in a Hard Place(1982) Done with Mirrors(1985) Rock in a Hard Place is the seventh studio album by American hard rock band Aerosmith, released on August 27, 1982, by Columb...

 

Environmental issues in the United Kingdom

Overview of the environmental issues facing the UK Compendium of UK Statistics - Environment This page lists the issues that the United Kingdom currently has that are related to the environment, such as pollution and contamination. In 2015, it was reported that for the past decade, the state of the environment in London had significantly deteriorated both in urban and rural areas. According to the UK NEA, grazing air pollution and the forces of climate change have significantly affected the m...

Maple syrup

Syrup made from the sap of maple trees Maple syrupBottled maple syrupPlace of originCanada United StatesMain ingredientsXylem sap (usually from sugar maple, red maple, or black maple) Cookbook: Maple syrup  Media: Maple syrup Maple syrup is a syrup made from the sap of maple trees. In cold climates, these trees store starch in their trunks and roots before winter; the starch is then converted to sugar that rises in the sap in late winter and early spring. Maple trees are tapped by dr...

 

Dialetto livinallese

Questa pagina sull'argomento linguistica sembra trattare argomenti unificabili alla pagina Lingua ladina. Puoi contribuire unendo i contenuti in una pagina unica. Commenta la procedura di unione usando questa pagina di discussione. Segui i suggerimenti del progetto di riferimento. Questa voce o sezione sull'argomento dialetti non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le line...

 

فترة الحضانة

فترة الحضانة[1] هي المدة الزمنية المنقضية بين التعرض لأحد الكائنات المسببة للمرض، مادة كيميائية أو إشعاع، وبين أول ظهور لأعراض وعلامات المرض. قد تكون هذه الفترة قصيرة بقدر دقائق أو لفترة طويلة جدا كثلاثين عاما في حالة من مرض كروتزفيلد جاكوب المتغير.[2] أمثلة لحالات ...

1917 Saskatchewan general election

Canadian provincial election 1917 Saskatchewan general election ← 1912 June 26, 1917 (1917-06-26) 1921 → ← outgoing membersmembers →62 seats in the Legislative Assembly of Saskatchewan32 seats needed for a majority   First party Second party   CON Leader William Martin Wellington Willoughby Party Liberal Conservative Leader since 1916 1912 Leader's seat Regina City Moose Jaw City Last election 45 8 Seats ...

 

ملسوقة

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