scattered-lenity

date-created: 2024-06-06 10:31:29 date-modified: 2024-07-10 10:06:25

o# Nicht Erkennbar / Nicht Entscheidbar anchored to 112.00_anchor_overview proceeds from 112.15_abzählbarkeit

Overview

Zuvor in 112.15_abzählbarkeit haben wir die abzählbare/ überabzählbare Definition von Mengen definiert und betrachtet.

Hierbei war / ist einsehbar, das es Mengen gibt, die in ihrer Konstruktion überabzählbar sind, obwohl ihre Obermenge das vielleicht nicht ist. [Indikatorfunktion $2mathbbN$](112.15_abzählbarkeit.md#Indikatorfunktion%20$2$)

Satz von Cantor | Mächtigkeit von Potenzmengen

Wir wollen jetzt noch weiter betrachten, wie etwa die Abhängigkeit zwischen der Mächtigkeit der Potenzmenge einer Menge und der Menge selbst betrachten. (Ferner werden wir auch noch sehen, dass man damit dann auch noch die Natürlichen Zahlen nur durch Potenzmengen definieren und zeigen kann.)

[!Definition] Satz von Cantor:

Der Satz sagt aus, dass jede Menge $M$ (auch die leere) echt weniger mächtig ist, als ihre Potenzmenge $\mathcal{P}(M)$. Es gilt also: $$\mid M\mid <\mid \mathcal{P}(M)\mid$$

Dafür existiert dann also keine(!) Einbettung in Form einer surjektiven Abbildung: $$e:M\to \mathcal{P}(M)$$

wie können wir das beweisen, was wäre ein Ansatz, um das zu zeigen? Was folgt aus dieser Betrachtung? #card

Angenommen eine mögliche Abbildung $e:M\to \mathcal{P}(M)$ existiert und sei surjektiv. Dann betrachten wir ferner die Menge $$A:=\{m\in M\mid m\notin \underbrace{e(m)}\text{ Elemente von }\mathcal{P}(M)\text{ also Teilmenge von M}\}\subset M$$

(Wir konstruieren also eine Menge, die Elemente aus der Grundmenge $M$ enthält, die folgend kein Element aus einer entsprechend abgebildeten Menge der Potenzmenge enthält ( Also $e(m)\in \mathcal{P}(M)$ wobei aber dann $m\in M$ )

Es folgt dadurch:

• $A$ ist also eine möglicherweise leere Teilmenge von $M$ und daraus folgt dann also, dass $A\in \mathcal{P}(M)$ ( weil wir ja Elemente aus $M$ aufnehmen und zu einer Menge füllen. Sie kann maximal $=M$ sein und ist sonst irgendeine Teilmenge und damit auch $\in \mathcal{P}(M)$!)
• Da jetzt die Abbildung $e$ surjektiv ist muss es entsprechend ein Urbild geben: $m_0\in M$ wobei dann $e(m_0)=A$ ist. Dadurch tritt ein Widerspruch auf! Kann $m_0$ selbst in $A$ sein?
• Falls $m_0\in A$, dann ist nach Definition die Menge $A:m_0\notin e(m_0)=A$
• Ferner aber auch $m_0\notin A$, dann folgt nach Definition $\overline{A}:m_0\in e(m_0)=A$

–> Beide Aussagen erzeugen einen Widerspruch!

Korollar | unendliche Unendlichkeit!

Weil wir jetzt gezeigt haben, dass eine Potenzmenge einer abzählbar unendlichen Menge definitiv mächtiger als sie ist, können wir den Begriff der Unendlichkeit nochmal weiter betrachten bzw sehen, dass man ihn “theoretisch skalieren kann”!

[!Definition] Kardinalität für “Unendlichkeiten”

Es gibt beliebig viele Stufen der Unendlichkeit. Also bildlich: $$\mathbb{N}<\mathcal{P}(\mathbb{N})<\mathcal{P}(\mathcal{P}(\mathbb{N}))<\dots$$ Grundsätzlich ist es aber schwer/nicht ganz möglich, verschiedene “Unendlichkeiten” einordnen und nach Größe sortieren zu können. –> Bislang haben wir keinen echten Begriff dafür, wie groß etwa $\mathcal{P}(\mathbb{N})$ eigentlich ist - was dessen Kardinalität ist.

Was folgern wir daraus, können wir eine gewisse Sortierung für die Kardinalität von “Unendlichkeiten bzw. Mengen, die diese darstellen”, erzeugen?, Bedenke, dass $\mid \mathcal{P}(\mathbb{N})\mid =2^{{\aleph }_0}=\mid \mathbb{R}\mid$ #card

Wir würden prinzipiell schon gerne die Mächtigkeit dieser Mengen darstellen oder irgendwie ordnen können. Dafür würden wir Kardinalzahlen verwenden, um sie ordnen zu können. Dabei setzen wir die Kardinalzahl ${\aleph }_0=|\mathbb{N}|$, da das die kleinste unendliche (abzählbare) Menge ist, die wir benennen können. Die nächst größere Kardinalität wäre nun ${\aleph }_1$ und wir würden diese gerne mit einer Menge knüpfen.

Wir wissen schon, dass $\mid \mathcal{P}(\mathbb{N})\mid \ge {\aleph }_0$ ist, (aber wir wissen nicht, inwiefern sie größer ist!) Weiterhin wissen wir, aus 112.14_abzählbarkeit, dass $\mid \mathcal{P}(\mathbb{N})\mid =2_{}^{{\aleph }_0}=|\mathbb{R}|$

Und somit haben wir **eiR}\mid$ ist, aber wissen es nicht.

–> Das beschreibt die Kontinuumshypothese !

Exkurs | natürliche Zahlen durch Cantors-Satz erzeugen:

John von Neumann hat ein mengentheoretisches Modell aufgebaut, welches unter Anwendung des Satzes von Cantor die natürlichen Zahlen konstruieren / erzeugen kann.

[!Bemerkung] Erzeugung von $\mathbb{N}$>>CantorsSatzgiltf\ddot{u}ralleMengen,alsoauchf\ddot{u}rdieleere!>Esgiltdabei$\mid \emptyset | = 0, |\mathcal{P}(\emptyset)\mid = | { \emptyset }\mid = 1$/>>Darausk\ddot{o}nnenwirjetztfolgendkonstruieren:>$$\begin{array}{rlrl}>0& :=& =\{\}& =\varnothing \\ >1& :=0^{\prime }& =\{0\}& =\{\varnothing \}\\ >2& :=1^{\prime }& =\{0,1\}& =\{\varnothing ,\{\varnothing \}\}\\ >3& :=2^{\prime }& =\{0,1,2\}& =\{\varnothing ,\{\varnothing \},\{\varnothing ,\{\varnothing \}\}\}\\ >n+1& :=n^{\prime }& =\{0,1,2,\dots ,n\}& =n\cup \{n\}>\end{array}$$>>-->Wirk\ddot{o}nnen$\mathbb{N}$also\ast \ast induktivaufMengen\ast \ast definierenundkonstruieren.>Dabei:>-istdienullteMenge,dieleereMenge>-die$n+1$-teMengeistdie\ast \ast Vereinigung\ast \ast derVorg\ddot{a}ngermengeundderMenge,diedieVorg\ddot{a}ngermengeenth\ddot{a}lt.>-M\ddot{o}glich,weildieVorg\ddot{a}ngermengeunddieMenge,welchedieseenth\ddot{a}lt,jeweilsdisjunktsind!(weilessichumeineeindeutigeStrukturbzwMengehandelt,diewirkonstruieren)>\ast \ast WirverwendenhierMengen\ast \ast dieandereMengenenthalte,n\ast \ast sichselbstabernicht\ast \ast .>>-->Istdannvielleicht$\mathbb{N}$ die Menge aller Mengen, die sich nicht selbst enthalten?

Dieser Gedanke, dass man eine Menge, die sich selbst nicht enthält, konstruieren kann, wird auch mit Russel’s Paradox beschrieben

(siehe Portal!, last resort when an AI has gained too much privileges )

Russel’s Paradox (1872 - 1970)

Wenn der Barbier alle Menschen rasiert, die sich nicht selbst rasieren, wer rasiert dann den Barbier?

[!Req] Paradox:

Betrachten wir die Menge von Elementen, die sich nicht selbst enthalten. $$R:=\{x\mid x\notin x\}$$>>Ist$R \in R$?????>-Falls$R \in R$,dannenth\ddot{a}ltsich$R$selbst,aberperDefinitionmussfolgen$R \notin R$>-Falls$R \notin R$,dannenth\ddot{a}ltsich$R$\ast \ast nichtselbst\ast \ast ,unddemnach$R \in R$>>Seidannalso:$R = { x \mid x \notin x }$danngiltfolgend:$R \in R \Longleftrightarrow R \notin R$>{>}_{w}asfolgernwirhieraus{?}_{>}>1.$R$istkeineMenge!\ast \ast Meistens\ast \ast enthaltensichMengennichtselbst.Etwaistdie\ast \ast Menge\ast \ast allerMenschenselbstkeinMensch!>2.vielleichtgibtessolcheMengen?Betrachtenwiretwa"dieMengeallerabstraktenIdeen".IstdanndieseBetrachtungaucheineabstrakteIdee?HilbertsBeschreibung(warumeineMenge,wieobigbeschriebennichtm\ddot{o}glichist):>MankanndieMengendanacheinteilen,obunterihrenElementendieMengeselbstvorkommtodernicht.Hierbeikannesdahingestelltbleiben,obes\ddot{u}berhauptm\ddot{o}glichist,dasseineMengeunterihreneigenenElementenvorkommt.JedenfallsabergibtessolcheMengendiesichselbstnichtalsElementeenthalten.>>Z.B.kanndieMengeallerMenschensichnichtselbstenthalten,dadieseMengedochnichtselbsteinMenschist.>>Esseinun$N$dieMengeallerMengen,diesichnichtalsElemententhalten.Dannsindf\ddot{u}r$N$selberMengennurzweiF\ddot{a}llezuunterscheiden:entwedergeh\ddot{o}rt$N$zudenMengen,diesichselbstnichtenthalten,oder$N$geh\ddot{o}rtzudenMengen,diesichselbstenthalten.BeideAnnahmenf\ddot{u}hrenjedochaufeinenWiderspruch.DennimerstenFallm\ddot{u}sstegem\ddot{a}ßDefinitionvon$N$dieMenge$N$unterihrenElementenvorkommen,w\ddot{a}hrenddieAnnahmediesausschließt.Imzweitendagegenw\ddot{u}rdedieMenge$N$alsElementeineMenge-n\ddot{a}mlichsichselber-enthalten,diesichselbstenth\ddot{a}lt,entgegenderDefinitionvon$N$.EsdarfdieseZeilenichtgeben!(Mankannesaberhinschreiben!!!)$$R:=\{x\mid x\notin x\}$$ ????

oder, wie Hilbert es poetisch geäußert hat:

[!Feedback] David Hilbert (1862 Königsberg–1943 Göttingen) Was sagen wir nun zu diesen Paradoxien? Nun, welche Stellung nahmen denn jene Klassiker des aktual Unendlichen (Cantor, Frege, Dedekind) ein? Das Bekanntwerden der Paradoxien wirkte katastrophal.

Cantor, wohl derjenige, der das Vorhandensein solcher Paradoxien zuerst selbsterkannt hatte, fasste sich am ehesten: durch Gewaltspruch verbannte er solche Mengen, wie wir sie dort gebraucht haben, aus seinem Paradiese: die Formel seines Bannfluches lautete: jenes sind inkonsistente Mengen, d. h. Mengen, deren Elemente niemals zusammengedacht werden dürfen; er traute sich die Fähigkeit zu, den Mengen ins Herz zuschauen und die Engel von den Teufeln zu unterscheiden.

Dedekind und Frege dagegen gaben tatsächlich den Kampf für ihren Standpunkt auf und erklärten sich als des Irrtums überführt

Zermelo-Fraenkel Mengenlehre

Um das Paradox zu umgehen und nicht mehr damit in Probleme zu geraten, muss man irgendwie eine bessere Mengenlehre definieren und erzeugen!

[!Definition] Zermelo-Fraenkel Mengenlehre

Es wird hier ein Aussonderungsaxiom definiert: Zu jeder Mange $A$undjedemPr\ddot{a}dikat$P(x)$,indemdieVariable$M$nichtvorkommt,existiertdieMenge$M$,welche\ast \ast genaudieElemente\ast \ast von$A$enth\ddot{a}lt,f\ddot{u}rdie$P(x)$gilt.Also:$$\forall A:\exists M:\forall x:(x\in M⟺x\in A\wedge P(x))$$

–> hier sieht man nochmal eine formale Definition die einen Algorithmus beschreiben kann!

Mit der ganzen Betrachtung der Mengenlehre, und den obigen Aussagen ( und der neuen Mengenlehre von Zermelo-Fraenkel) möchte man eigentlich einen Algorithmus und eine gewisse Formalität neu definieren / erweitern, sodass dann Fehler / Paradoxe vermieden oder weniger stark auftreten (können)

Dieses Konzept können wir ferner in unsere Betrachtung von Maschinen und abstrakten Konstrukten, die berechnen und konstruieren können übernehmen und somit diverse Probleme einsehen, Limits setzen und definieren können.

Kontinuumshypothese

Wir haben uns zuvor in Erkenntnis schonmal angeschaut, dass jede Potenzmenge einer abzählbaren Menge echt mächtiger ist als sie. Dabei konnten wir aber nicht wirklich ausmachen, ob sie jetzt echt größer/kleiner $\mathbb{R}$istodernicht.GenaudasFormuliertHilbertauchinseinem\ast \ast erstenProblem\ast \ast :>[!Req]Hypothese>>(Gem\ddot{a}ßHilbertsProblem):\ast \ast Gibt\ast \ast eseine\ddot{u}berabz\ddot{a}hlbareTeilmengevon$\mathbb{R}$,dieinihrerM\ddot{a}chtigkeit\ast \ast echtkleiner\ast \ast$\mathbb{R}$ist?>>(AusunsrervorherigenBetrachtung)fragtG\ddot{o}del\ddot{a}hnliches:IstjedeunendlicheTeilmenge$M$von$\mathbb{R}$gleichm\ddot{a}chtigzu$\mathbb{R}$oderzu$\mathbb{N}$??Formal:>$$\mid \mathbb{N}\mid <\mathcal{P}(\mathbb{N})=\mathbb{R}<\mathcal{P}(\mathcal{P}(\mathbb{N}))<\dots ;{\aleph }_0<{\aleph }_1=\mid \mathbb{R}\mid ??$$

Was folgt aus dieser Betrachtung, kann man sie bestimmen, gibt es eine Lösung? #card

Gödel konnte 1938 zeigen, dass die Kontinuumshypothese mit den Axiomen der Mengenlehre ( Zermelo-Fraenkel + Auswahlaxiom und ZFC) nicht widerlegt werden kann.

Wenn also $ZFC$widerspruchsfreiist,dannistauch$ZFC +CH$widerspruchsfrei!>>WeiterhinwurdevonPaulCohen(1960)gezeigt,dassdieHypothesemit$ZFC$ nicht bewiesen werden kann

–> Wir folgern daraus dann: Mit den Mitteln der Mengenlehre können wir die Kontinuumshypothese also nicht entscheiden!

Wir können uns nur für eine Seite entscheiden und annehmen, dass sie stimmt/ oder nicht.

( Prof Dr. Hennig hat vor Wochen in der katholischen Fakultät ähnliches vorgestellt und da haben die Personen, mit ihrem stark denkenden Hintergrund (halt aufgrund ihrer theoretischen Natur lol), dann dieses Konzept eingebracht. “Da hat das Denken bei denen angefangen”. Ferner meinte er, dass wir hier den Vorteil haben, dass wir zwischen Fakultäten kommunizieren können ( da es keine technische Uni ist) und meinte, dass man mit den Kommiliton*innen sprechen kann ( kurzer (guter!) Angriff: wobei es primär nur Kommilitonen sind))

Bezug zu Sprachen | Maschinen

Wir wissen jetzt also, dass es abzählbar viele Worte in der Kleen’schen Hülle $\Sigma^{}$gibt(\ddot{u}bereinemendlichenAlphabet$\Sigma,\mid \Sigma\mid >0$)Weiterhinenth\ddot{a}ltdannjedeSprache$L \in \Sigma^{}$alsoh\ddot{o}chstensabz\ddot{a}hlbarvieleWorte.Aberesgibtweiterhin-waswirjaschonbewiesenhabe-\ast \ast \ddot{u}berabz\ddot{a}hlbarvieleSprachen\ast \ast ,denn$\mathcal{P}(\Sigma^{*}) > |\mathbb{N} |$!

Gleichzeitig wissen wir aber auch, dass es nur abzählbar unendlich viel Turingmaschinen gibt Eigenschaften der Codierung. und somit auch nur abzählbar viele Entscheider!

[!Attention] Folgerung aus Begrenzung von TMs und überabzählbaren Sprachen

Es gibt also abzählbar viele Worte in der kleen’schen Hülle und es gibt für ein Alphabet überabzählbar viele Sprachen

Was lässt sich aufgrund der zwei Prämissen folgern? #card

Es muss Sprachen in $\mathcal{P}(\Sigma^{}) \setminus RE$geben,die\ast \ast vonkeinerTMerkanntwerden\ast \ast !>>Wiesiehteinesolche\ast \ast Sprache\ast \ast$D \in \mathcal{P}(\Sigma^{})\setminus RE$nunaus?Kannmansiekonstruieren?>>GibtesSprachen$L \in RE \setminus R$ die wir erkennen, aber nicht entscheiden können?

Diagonalsprache | $\notin RE$>[!Definition]Diagonalsprache>>WirwolleneineSprachebetrachten,dieebennichtrekursivaufz\ddot{a}hlbarist(somitvonkeinerTMerkannt/entschiedenwerdenkann!)>>WirkonstruierendieSprachefolgend:>>-Seien$w_{1},w_{2},\dots$dannalleW\ddot{o}rter\ddot{u}berdemAlphabet$\Sigma$(wirwissen,dassesnurabz\ddot{a}hlbarvieledavongibt,alsokannmansieentsprechendnummerieren!)>-Seidann$M_{1},M_{2},\dots$die\ast \ast FolgevonTuringmaschinen\ast \ast (nummeriertdurchdieG\ddot{o}delnummer)>-Wirk\ddot{o}nnendanneine\ast \ast Diagonalsprache\ast \ast bestimmen(die\ddot{a}hnlich,wiedieIndikatorfunktion,diewirzuvorbeschriebenhaben!)$$d_{ij}=\{\begin{array}{ll}1& \text{ falls }{M}_i\text{ das Wort akzeptiert}{w}_j\\ 0\text{ sonst}& \end{array}$$>>Wirdefinierensiejetztfolgend:$D = { w_{i} \mid d_{ii}=0 }$

was beschreibt diese Sprache, wie wird man damit jetzt zeigen können, dass sie nicht rekursiv aufzählbar ist? #card

Wir führen jetzt quasi jedes Wort über das Alphabet $\Sigma$ auf jeder Turingmaschine aus und schauen, was hierbei resultiert (akzeptiert, oder nicht (oder hält nicht ^^))

Durch diese Konstruktion können wir den Beweis in einer Tabelle betrachten und erkennen:

• in der $i$-tenZeilestehtder\ast \ast Indikatorvektor\ast \ast dervon$M_{i}$akzeptiertenSprache(alsoobsieakzeptiertwurdeodernicht)>-Dabeigiltjetztf\ddot{u}ralle$i \in \mathbb{N}$:D\ast \ast wirdnichtvon\ast \ast$M_{i}$erkannt,\ast \ast denn\ast \ast >-Falls$M_{i}$dasWort$w_{i}$akzeptiert,dannist$w_{i} \notin D$(gem\ddot{a}ßderDefinition,dassesdaverwerfenmuss)unddeshalbistdann$M_{i}$nichtdie\ast \ast TM\ast \ast ,die$D$erkennenkann>-\ast \ast Weiterhin\ast \ast :Wenn$w_{i} \in D$,dannerkennt$M_{i}$diesesWortnicht(gut!),undistdamit\ast \ast auchnichtdieTM\ast \ast ,die$D$erkennt(weilesjahiernichtfunktionierthat).>>Dadurchfolgt\ast \ast esgibtkeineTM\ast \ast ,die$D$ erkennen kann!

Die Diagonalsprache ist also eine solche Sprache, die nicht entscheidbar/erkennbar ist, weil wir hier mit dem Halteproblem kollidieren und dadurch ein Problem entsteht.

Folgerung aus der Diagonalsprache

Mit der obigen Konstruktion haben wir gezeigt, dass es Sprachen außerhalb von $RE$gibt(rekursivaufz\ddot{a}hlbar).$D$wargenausoeinBeispieldaf\ddot{u}r!($D$ ist nicht wirklich greifbar, weil sie sehr theoretisch ist. Gibt es dafür explizite Wörter?)

Nein, denn sonst hätten wir eine Idee/ einen Ablauf gefunden, der diese Worte beschreiben könnte und damit wäre eine TM möglich, die diesen Ablauf umsetzt!

Problem mit expliziten Worten $w \in D$:K\ddot{o}nnenwirnichtversucheneineTMzubauen,die$D$\ast \ast wenigstens\ast \ast erkennenkann?EinAnsatzdaf\ddot{u}r:>[!Example]>AufeineEingabe$w$:>-Findeheraus,welcheNummer$w$inderListeallerW\ddot{o}rterist-->f\ddot{u}rwelches$i_{0}$gilt$w = w_{i_{0}}$(Dask\ddot{o}nnenwireinfachpr\ddot{u}fen:durchdiechronologischeSortierunggehenundaufz\ddot{a}hlen,dannbeimTrefferdieZahlausgeben)>-KonstruieredieTuringmaschine$M_{i_{0}}$(diedasWorterkennensollte)-->(k\ddot{o}nnenwirmitderUniversellenTuringmaschinemachen!)>-Wendejetzt$\langle M_{i_{0}} , w_{i_{0}} \rangle$ an (also die UTM, die darauf simuliert)

Warum ist das nicht möglich, welches Problem tritt auf? #card

Sei jetzt $M_{D}$diegebauteMaschine-die$D$erkennensoll.>Fernerist$i_{0}$derIndexvon$M_{D}$inderListe\ast \ast allerTMS\ast \ast und$w_{i_{0}}$dasWort\ast \ast inderListeallerW\ddot{o}rter\ast \ast .>>Wennwirjetzt$\langle M_{i_{0}} , w_{i_{0}} \rangle$anwendenw\ddot{u}rden,k\ddot{a}meeszueinemWiderspruch:>-$M_{i_{0}}$akzeptiert$w_{i_{0}} \implies M_{D}$akzeptiert$w_{i_{0}}$\ast \ast nicht\ast \ast (aufgrundderKonstruktion)\ast \ast Dennoch\ast \ast$M_{D} = M_{i_{0}}$(denndiePositioninderListederTMspasst)>-\ast \ast Weiterhinaberauch\ast \ast :$M_{i_{0}}$akzeptiert$w_{i_{0}}$\ast \ast nicht\ast \ast$\implies M_{D}$akzeptiert$w_{i_{0}}$(lautKonstruktion)\ast \ast Dennoch\ast \ast$M_{D}= M_{i_{0}}$(unddasgehtnicht,weilbeidejaeigentlichgleichsind,dieeineaberakzeptiert/dieanderenicht!)>DieseErkenntniskannmanjetztverschiedenInterpretieren!>[!Feedback]Folgerung>>1.EsgibtnichtgenugTuringmaschinen,um$M_{D}$bauenzuk\ddot{o}nnen(weilsiejaf\ddot{u}r\ast \ast jedesWort\ast \ast eineTMfordert!)>2.Da\ast \ast Turingmaschinen\ast \ast teilsaucheinfach\ast \ast nichthaltenk\ddot{o}nnen\ast \ast ,k\ddot{o}nnenwirdasKomplementeinerrekursivaufz\ddot{a}hlbarenSprache\ast \ast nichtdirektkonstruieren\ast \ast (dennwirk\ddot{o}nnen3m\ddot{o}glicheZust\ddot{a}nde,wobeidereineundefiniertist,nichteinfach"invertieren")>3.DasKomplementvon$D$istdas\ast \ast spezielleHalteproblem!\ast \ast [112.17_{r}eduktionen](112.17_{r}eduktionen.md)$$K=\{w\mid M_w\text{ ha¨lt auf }w\}$$ ( was erkennbar ist, wie wir wissen)

$A_{TM}$

<< ))– Das Halteproblem –(( >>

[!Definition] Halteproblem durch eine Sprache

Sei $\langle M, w \rangle \in { 0,1 }^{*}$ das Wort, dass die Gödelnummer der TM $M$mitdemWort$w$ konkateniert ( also einfach diese beiden Parameter verbindet und mit einem Wort beschreibt; dass man sie aufteilen kann, wissen wir, da Codierbarkeit eindeutig)

Wie konstruieren wir die Sprache $A_{TM}$ richtig? Was können wir über sie aussagen? #card

Wir betrachten jetzt die Sprache $T_{\cup}$:$$A_{TM}:=\{⟨M,w⟩\mid M\text{ ist der Code einer TM und }w\text{ wird von M akzeptiert}\}$$>>\ast \ast Esfolgt\ast \ast :$A_{TM} \in RE$-->sieistrekursivaufz\ddot{a}hlbar!>>KonstruierenwireineTM,die$A_{TM}$rekursivaufz\ddot{a}hlt!>>-->DasistdieuniverselleTuringmaschine$U$[112.14_{u}niversa{l}_{t}urin{g}_{m}achine](112.14_{u}niversa{l}_{t}urin{g}_{m}achine.md)welchewirsokonstruierthaben,dasssiezweiOutcomeshat:>-$x \in A_{TM} \implies U$akzeptiert>-$x \notin A_{TM} \implies U$verwirftoder\ast \ast stopptnicht\ast \ast >>IndieserPr\ddot{a}misse,dasssie\ast \ast eventuellnichtstoppt\ast \ast ,liegtjetzteinProblem:>>>>[!Question]GibteseineTM$H$dieverwirft,wenn$U$verwirftodernichtstoppt?(alsoimmerhaltenkann?)\ast \ast Folgerung\ast \ast dazu:>[!Beweis]$A_{TM} \notin R$ -> also nicht entscheidbar

Wie können wir beweisen, dass die TM nicht entscheidbar ist?? #card

Unter Anwendung des 2ten Cantor’schen Diagonalargument können wir diese Aussage beweisen:

Sei $A_{TM}$\ast \ast entscheidbar\ast \ast durcheineTM$H$.also$$H(⟨M,w⟩)\{\begin{array}{ll}>\text{ akzeptiert}& \text{ falls M das Wort w akzeptiert}\\ >\text{ verwirft}& \text{ falls M das Wort nicht akzeptiert (oder nicht anha¨lt)}>\end{array}$$>>Wirwissen,dass$H$immer$\forall w \in { 0,1 }^{*}$h\ddot{a}lt.Betrachtenwiraber:$\langle M_{i}, \langle M_{j}\rangle \rangle,i,j \in \mathbb{N}$.(alsowirwendendieG\ddot{o}delnummerjederTMaufjederTMan,undschauen,obsieakzeptiert/odernicht)>>Wirbetrachtenindieser\ast \ast tabellarischenAuflistung\ast \ast \ast \ast spezifischdieDiagonale\ast \ast .-->Dasgibtan,wiedieTM$M_{i}$aufdenCode$\langle M_{i} \rangle$reagiert(sichselbstakzeptiert).>>WirbauenjetztdieTM$D_{TM}$wiefolgt:>-$D_{TM}$nimmtCodes$\langle M \rangle$alsEingabe>-$D_{TM}$nutzt$H$um$\langle M, \langle M\rangle\rangle$zuberechnen\ast \ast und\ast \ast gibtdanndasGegenteilzur\ddot{u}ck!>>>(wirdalsoeinfachpassendinvertiert)>>\ast \ast Esfolgt\ast \ast :>-Falls$D_{TM}(\langle D_{TM}\rangle)= accept$(AlsoAnwendungaufsichselbst(inderDiagonalsprachealsoder$i$teEintrag,wosiedas$i$teWortbearbeitet))\ast \ast dann\ast \ast m\ddot{u}ssteinderTabellevon$H$nachaufdem$\langle D_{TM}\rangle$-tenEintragein\ast \ast accept\ast \ast stehen-->aberdannw\ddot{u}rdedie\ast \ast Turingmaschine\ast \ast gem\ddot{a}ßihrerDefinition\ast \ast eigentlichverwerfen!\ast \ast (weilsiejadieDiagonalen\ast \ast invertiert!\ast \ast )>-Fallsdannalso$D_{TM}(\langle D_{TM}\rangle)= reject$,danngiltdasgleichanalog->siem\ddot{u}ssteihren\ast \ast berechnetenZustand\ast \ast invertieren,wasdannabernichtmehrder\ast \ast berechneteZustandist\ast \ast -->damithabenwiretwas"oszillierendeserzeugt(quasi)">>(Dieses\ast \ast Argument\ast \ast funktioniert,weilwirhiereineneueTMdefinieren,welche\ast \ast jaauchwiederinderTabelle\ast \ast aufkommenwird(weilwirja\ddot{u}beralleTMsabbilden)).Dadurch,dasswirebenaufalleabbildenundsomitauchaufdiese\ast \ast widerspr\ddot{u}chliche\ast \ast (spezifischerauchaufdenInhalt$w_{i}$(beisichselbst),wowirabersagen,dasssieinderDiagonaleneingabe\ast \ast immerdasInversenehmensoll\ast \ast (undsomitbeisichselbstdanneigentlicheineEingabe$X$rauskommt,sieabergem\ddot{a}ßderDefinition$\overline{X}$ nehmen “muss”, geht das nicht mehr ganz auf und failed! ))