Retraceable Menge

Eine Menge natürlicher Zahlen heißt retraceable (engl.: zurückverfolgbar), wenn zu jedem Element der Menge das nächstkleinere Element berechnet werden kann. Retraceable Mengen treten in der theoretischen Informatik, genauer der Berechenbarkeitstheorie, bei der Untersuchung entscheidbarer Mengen auf. Die Theorie der retraceablen Mengen geht auf Arbeiten von Dekker und Myhill zurück.^[1]^[2]

Erklärung

Motivation

Für entscheidbare Mengen $A=\{a_{0}<a_{1}<a_{2}<\dots \}\subseteq \mathbb {N}$ sind die folgenden beiden Funktionen $f$ und $g$ stets berechenbar:

Für alle $n$ sei $f(a_{n})=a_{n+1}$ , es sei denn $A$ ist endlich und $a_{n}=\max A$ , dann gelte $f(a_{n})=a_{n}$ .
Für alle $n$ sei $g(a_{n+1})=a_{n}$ sowie $g(a_{0})=a_{0}$ .

Außerhalb von $A$ können die Funktionen dabei ein beliebiges Verhalten zeigen. Nun ist die in 1. definierte Funktion $f$ genau dann berechenbar, wenn $A$ entscheidbar ist. Es stellt sich daher die Frage, ob eine ähnliche Charakterisierung auch für diejenigen Mengen gelingt, für die $g$ berechenbar ist. Dies sind gerade die retraceable Mengen.

Definition

Eine Menge $A=\{a_{0}<a_{1}<a_{2}<\dots \}\subseteq \mathbb {N}$ natürlicher Zahlen heiße retraceable, falls es eine partiell berechenbare Funktion $g\colon \mathbb {N} \rightsquigarrow \mathbb {N}$ gibt, so dass $(\forall n\colon g(a_{n+1}){\downarrow }=a_{n})\land g(a_{0}){\downarrow }=a_{0}$ . Die Abbildung $g$ heißt dann retraceable Funktion.

Eigenschaften

Entscheidbare Mengen sind offensichtlich retraceable (s. o.), allerdings gilt die Umkehrung im Allgemeinen nicht. Stattdessen gilt:

Retraceable Mengen sind stets entweder entscheidbar order immun.
Retraceable Mengen mit rekursiv aufzählbarem (r.e.) Komplement sind entweder entscheidbar oder sogar hyperimmun.

Dennoch lässt sich eine Charakterisierung entscheidbarer Mengen finden, die die retraceable Eigenschaft benutzt.

Eine Menge ist genau dann entscheidbar, wenn sowohl sie selbst als auch ihr Komplement retraceable ist.

Betrachtet man nur relative Entscheidbarkeit ergibt sich das folgende Bild:

Eine retraceable Menge ist entweder endlich (also per se entscheidbar) oder in allen ihren unendlichen Teilmengen relativ entscheidbar.
Es gilt also, ist $A$ retraceable und hat eine unendliche Teilmenge $B\subseteq A$ , so folgt $A\leq _{T}B$ (vgl. Reduktion).

In der obigen Definition ist das Verhalten der retraceable Funktion $g$ außerhalb von $A$ unbestimmt, insbesondere muss die Funktion dort nicht definiert sein. Es gibt jedoch Fälle, in denen man $g$ total wählen kann.

Retraceable Mengen mit r.e. Komplement haben totale retraceable Funktionen.

Natürlicherweise gibt es einen engen Zusammenhang zwischen retraceable Mengen und alternativen berechenbaren Ordnungen auf den natürlichen Zahlen.

Hinweis: Semi-Berechenbarkeit sollte nicht mit Semi-Entscheidbarkeit verwechselt werden.

Jede unendliche semi-berechenbare Menge hat eine unendliche retraceable Teilmenge.
Retraceable Mengen mit r.e. Komplement sind semi-berechenbar.

In der Theorie der Turing-Grade liefern die retraceable Mengen eine Klasse universeller Repräsentanten:

Jeder Turing-Grad enthält eine retraceable Menge.
Jeder rekursiv aufzählbare Turing-Grad enthält eine retraceable Menge, deren Komplement r.e. ist.

Einzelnachweise

↑ J.C.E. Dekker, J. Myhill: Retraceable sets. In: Canadian Journal of Mathematics. Band 10. Canadian Mathematical Society, Ottawa, CAN-ON 1958, S. 357–373.
↑ J.C.E. Dekker: Infinite series of isols. In: Proceedings of Symposia in Pure Mathematics. Band 5. American Mathematical Society, Providence, US-RI 1962, S. 77–96.

Literatur

H. Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
P. Odifreddi: Classical Recursion Theory. Elsevier, 1989, ISBN 0-444-87295-7.

Read other articles:

Room and pillar mining

Horizontal excavation mining method Room and pillar or pillar and stall is a variant of breast stoping. It is a mining system in which the mined material is extracted across a horizontal plane, creating horizontal arrays of rooms and pillars. To do this, rooms of ore are dug out while pillars of untouched material are left to support the roof – overburden. Calculating the size, shape, and position of pillars is a complicated procedure, and is an area of active research.[1] The techn...

Lavoslav Ružička

Lavoslav RužičkaLeopold Ružička.BiographieNaissance 13 septembre 1887VukovarDécès 26 septembre 1976 (à 89 ans)MammernSépulture Cimetière de FlunternNom dans la langue maternelle Lavoslav (Leopold) RužičkaNationalités austro-hongroisesuisseFormation Institut de technologie de KarlsruheActivités Chimiste, professeur d'universitéAutres informationsA travaillé pour Université d'Utrecht (10 novembre 1926 - 25 septembre 1929)École polytechnique fédérale de Zurich (1918-1957)...

Craig Lewis (cyclist)

American cyclist Craig LewisLewis at the 2013 Tour of AlbertaPersonal informationBorn (1985-01-10) January 10, 1985 (age 39)Moore, South Carolina, United States of AmericaHeight5 ft 10 in (1.78 m)Weight143 lb (65 kg)Team informationCurrent teamRetiredDisciplineRoadRoleRiderAmateur team2004–2006TIAA–CREF Professional teams2007Slipstream–Chipotle2008–2011Team High Road2012–2013Champion System[1] Craig Lewis (born January 10, 1985) is an Ameri...

Bekir Çoban-zade

Crimean Tatar poet and Turkologist Bekir Vaap oğlu Çoban-zadeBorn27 May [O.S. 15 May] 1893QarasuvbazarDied13 October 1937 (aged 44)BakuAlma materUniversity of Budapest Bekir Vaap oğlu Çoban-zade (pronounced [tʃobanzade], 27 May [O.S. 15 May] 1893 – 13 October 1937) was a Crimean Tatar poet and professor of Turkic languages who was one of the victims of the Great Purge. In the midst of a successful academic career, at the age of 44, �...

Aeronca L-3 Grasshopper

Pour les articles homonymes, voir L-3. Aeronca L-3C Grasshopper Aeronca L-3B Grasshopper Constructeur Aeronca Rôle Avion de reconnaissance et de liaison Statut Retiré du service Mise en service 1941[1] Équipage 2 Motorisation Moteur Continental O-170-3 (en) Nombre 1 Type Moteur à hélice tractive Puissance unitaire 65 ch Dimensions Envergure 10,67 m Longueur 6,4 m Hauteur 2,34 m Surface alaire 14,68 m2 Masses À vide 379 kg Maximale 590 kg Performances ...

Angkatan Bersenjata Azerbaijan

Angkatan Bersenjata AzerbaijanAzərbaycan Silahlı QüvvələriLambang Angkatan Bersenjata AzerbaijanDidirikan26 Juni 1918Formasi terkini9 Oktober 1991Angkatan Angkatan Darat Angkatan Udara Angkatan LautMarkas besarBaku, AzerbaijanKepemimpinanPanglima Tertinggi Presiden Ilham AliyevMenteri Pertahanan Koljen Zakir HasanovKepala Staf Letjen Karim ValiyevKekuatan personelUsia penerimaan18–35 (Reguler)Wajib militer12–18 bulan untuk angkatan darat[1]Ketersediaanmenurut usia3....

22 mm grenade

Size of rifle grenade 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: 22 mm grenade – news · newspapers · books · scholar · JSTOR (May 2020) (Learn how and when to remove this message) M7 grenade launcher with 22 mm grenade fitted on the end of an M1 Garand rifle. Yugoslavian M59/66 (SKS) with a 22 mm launch...

Hubert Curien

French physicist Hubert CurienMinister of Research and TechnologyIn office1984–1986PresidentFrançois MitterrandPrime MinisterLaurent FabiusPreceded byNicole CathalaSucceeded byRobert Chapuis Personal detailsBorn(1924-10-30)30 October 1924Cornimont, FranceDied6 February 2005(2005-02-06) (aged 80)Loury, FranceSpousePerrine DumézilChildren3EducationLycée Saint-LouisAlma materÉcole normale supérieureOccupationPhysicistAwardsHonda Prize (1998)Allan D. Emil Memorial Award (1993) Solvay ...

Refrigerator

Appliance for cold food storage For other uses, see Refrigerator (disambiguation) and Fridge (disambiguation). Food in a refrigerator with its door open Exterior of a modern refrigerator A refrigerator, colloquially fridge, is a commercial and home appliance consisting of a thermally insulated compartment and a heat pump (mechanical, electronic or chemical) that transfers heat from its inside to its external environment so that its inside is cooled to a temperature below the room temperature....

Rose Pesotta

American trade unionist (1896–1965) Rose PesottaPesotta addresses the floor at the 1965 ILGWU conventionRose Pesotta (1896–1965) was an anarchist, feminist labor organizer and vice president within the International Ladies' Garment Workers' Union. Part of a series onAnarchism History Outline Schools of thought Feminist Green Primitivist Social ecology Total liberation Individualist Egoist Free-market Naturist Philosophical Mutualism Postcolonial African Black Queer Religious Christian Jew...

Disinvestment from Israel

Economic boycott campaign against Israel Disinvestment from Israel is a campaign that aims to use disinvestment to pressure the government of Israel to put an end to the Israeli occupation of Palestinian territories captured during the 1967 military campaign. The disinvestment campaign is related to other economic and political boycotts of Israel. A notable campaign was initiated in 2002 and endorsed by South Africa's Desmond Tutu.[1] Tutu said that the campaign against Israel's occup...

20 грудня

← грудень → Пн Вт Ср Чт Пт Сб Нд 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 2024 рік 20 грудня — 354-й день року (355-й у високосні роки) у григоріанському календарі. До кінця року залишається 11 днів. Цей день в історії: 19 грудня�...

أردبيل

أردبيل - مدينة - أردبيل اللقب دارالارشاد، دارالملك، دارالعرفان، دارالامان و شهر مقدس تاريخ التأسيس 705 (منذ 1319 سنة) تقسيم إداري البلد إيران [1][2] عاصمة لـ محافظة أردبيلمقاطعة أردبيل بلد إيران محافظة محافظة أردبيل خصائص جغرافية إحداثيات 38°15′00″N 48°17...

Mudgee

For the wine region named Mudgee, see Mudgee wine region. Town in New South Wales, AustraliaMudgeeNew South WalesView of the town centre, showing War Memorial Clock TowerMudgeeCoordinates32°35′43″S 149°35′16″E / 32.595174°S 149.587805°E / -32.595174; 149.587805Population11,457 (2021)[1]Postcode(s)2850Elevation454 m (1,490 ft)Location 270 km (168 mi) NW of Sydney 128 km (80 mi) ESE of Dubbo 192 km (119 mi)...

Mitsubishi Eclipse

Mitsubishi EclipseDescrizione generaleCostruttore Mitsubishi Motors Corporation Tipo principaleCoupé Altre versionispider Produzionedal 1989 al 2011 Sostituisce laMitsubishi Cordia NHTSA (1990[1]) Altre caratteristicheDimensioni e massaLunghezza4565 mm Larghezza1835 mm Altezzada 1360 a 1390 mm Passo2575 mm Massada 1340 a 1433 kg AltroAssemblaggioNormal (Illinois) USA Stessa famigliaMitsubishi Galant Auto similiAlfa Romeo BreraHonda IntegraToyota Cel...

Trabzonspor Kulübü

TrabzonsporCalcio Bordo-Mavililer (bordeaux-celesti)Karadeniz Firtinasi (tempesta del Mar Nero) Segni distintiviUniformi di gara Casa Trasferta Colori sociali Bordeaux, celeste InnoTrabzonspor Marşı Dati societariCittàTrebisonda Nazione Turchia ConfederazioneUEFA Federazione TFF CampionatoSüper Lig Fondazione1967 Presidente Ertuğrul Doğan Allenatore Şenol Güneş StadioŞenol Güneş(40.782 posti) Sito webwww.trabzonspor.org.tr PalmarèsTitoli nazionali7 Campionati turchi Trofei n...

12月12日

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: 12月12日 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年12月) 2024年12月（師走）日月火水木金土 1 2 3 4 5 6 7 8...

Radamisto (Handel)

Opera by George Frideric Handel This article is about Handel's opera. For the historical person upon whom the libretto is based, see Rhadamistus. George Frideric HandelRadamisto (HWV 12) is an opera seria in three acts by George Frideric Handel to an Italian libretto by Nicola Francesco Haym, based on L'amor tirannico, o Zenobia by Domenico Lalli and Zenobia by Matteo Noris. It was Handel's first opera for the Royal Academy of Music. The opera's plot is loosely based on the account of Rhadami...

Bridget of Sweden

Swedish nun, mystic, and saint (c.1303–1373) For Swedish royalty, see Bridget of Sweden (disambiguation). SaintBridget of SwedenOSsSAltarpiece in Salem church, Södermanland, Sweden (digitally restored)WidowBornc. 1303Uppland, SwedenDied23 July 1373 (aged 69–70)Rome, Papal StatesVenerated inCatholic ChurchAnglican CommunionLutheranism[1]Canonized7 October 1391 by Pope Boniface IXMajor shrineVadstena AbbeyFeast23 July8 October (General Roman Calendar of 1960)7 O...

Toronto—St. Paul's (federal electoral district)

Federal electoral district in Ontario, Canada This article is about the Canadian federal electoral district. For the provincial electoral district, see Toronto—St. Paul's (provincial electoral district). For the municipal electoral district, see Ward 12 Toronto—St. Paul's. Toronto—St. Paul's Ontario electoral districtLocation in TorontoFederal electoral districtLegislatureHouse of CommonsMP Don StewartConservativeDistrict created1933First contested1935Last conteste...

/profillengkap.com/index.php/article/Highwaymen Motorcycle Club

/profillengkap.com/index.php/article/1996 NCAA Division I women's volleyball tournament

Occidental Petroleum

Hiakinthos

Lollu Sabha Jeeva

Washington, Connecticut

العلاقات الجنوب سودانية النيجيرية

Direction générale de l'armement

WJLK (AM)

George Best (chronicler)

Tim nasional sepak bola wanita Panama

العلاقات المالية النيجيرية