{"id":2368,"date":"2013-07-07T10:28:06","date_gmt":"2013-07-07T08:28:06","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=2368"},"modified":"2025-11-25T21:50:47","modified_gmt":"2025-11-25T20:50:47","slug":"tia-bild-und-projektionssatz-lernziele-ke6-24","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=2368","title":{"rendered":"TIA: Bild- und Projektionssatz (Lernziele KE6 2\/4, Update)"},"content":{"rendered":"<p><strong>Update<\/strong>: Schnitzer im Projektionssatz aufgefallen. Fixed.<\/p>\n<p>Als ich die letzten Beitr\u00e4ge zu Kurseinheit 5 von TIA durchgegangen bin, ist mir aufgefallen, dass einige Beweise doch noch nicht so nachvollziehbar sind, wie ich das gerne h\u00e4tte.<\/p>\n<p>Nach dem Editieren kam ich auf eine Seitenzahl von \u00fcber 20. Schon wieder. Da blieb mir also nichts anderes \u00fcbrig, als den Beitrag zu KE6 erneut zu trennen. Schwierigkeiten machten mir aber die Kommentare zu den Lernzielen als alles noch ein einzelner Beitrag war. Diese zu verschieben war ohne manuellen Eingriff in die Datenbank nicht m\u00f6glich.<\/p>\n<p>Solltet Ihr daher auf Kommentare treffen, die nicht unbedingt zu dem Beitrag hier passen: meine Schuld. Sie geh\u00f6ren dann zu einem der drei anderen.<\/p>\n<p>Dieser Artikel ist brandneu und die anderen Beitr\u00e4ge zu KE6 sind teilweise massiv \u00fcberarbeitet worden. Eine erneute Lekt\u00fcre k\u00f6nnte sich also lohnen wenn Ihr bei KE6 der theoretischen Informatik A noch strauchelt und den Sachverhalt gerne mal in anderen Worten gelesen h\u00e4ttet.<\/p>\n<p>Lange Rede, kurzer Sinn: Das sind also die Beitr\u00e4ge zu Kurseinheit 6.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=2313\">TIA: Rekursive und rekursiv-aufz\u00e4hlbare Mengen (Lernziele KE6, 1\/4)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=2368\">TIA: Bild- und Projektionssatz (Lernziele KE6 2\/4)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=1117\">TIA: Halte- \u00c4quivalenz- und Korrektheitsproblem, Reduzierbarkeit, Satz von Rice (Lernziele KE6, 3\/4)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=1178\">TIA: G\u00f6del&#8217;scher Unvollst\u00e4ndigkeitssatz (Lernziele KE6, 4\/4)<\/a><\/li>\n<\/ul>\n<p>Dieser dreht sich komplett um den Bild- und Projektionssatz. Urspr\u00fcnglich war er nicht einmal eine halbe Seite lang. Als ich den Beweis dann Schritt f\u00fcr Schritt nachvollzog, wuchs er auf die aktuelle Gr\u00f6\u00dfe heran. Tja, und da ist er nun.<\/p>\n<h2>Lernziel 5<\/h2>\n<p style=\"padding-left: 30px;\"><em>Charakterisierung der r.a. Mengen durch Bild- und Projektionssatz<\/em><\/p>\n<p>Die Charakterisierung ist wie folgt definiert:<\/p>\n<blockquote><p>1. \\(A \\subseteq \\mathbb{N}\\) ist r.a. gdw. \\( A = \\emptyset\\) oder \\(A = Bild(g)\\) f\u00fcr ein \\(g \\in R^{(1)}\\)<\/p>\n<p>2. \\(A \\subseteq \\mathbb{N}^k\\) ist r.a. gdw. es eine rekursive Menge \\(B \\subseteq \\mathbb{N}^{k+1}\\) gibt mit \\(A = \\{x \\in \\mathbb{N}^k \\mid (\\exists t)(x,t) \\in B\\}\\)<\/p><\/blockquote>\n<p>Nr. 1 bedeutet, dass eine Menge \\(A\\) dann rekursiv ist, wenn sie von einer totalen, rekursiven Funktion \\(g\\) aufgez\u00e4hlt werden kann, d.h. dass \\(A\\) Bild dieser Funktion ist.<\/p>\n<p>Nr. 2 ist der Projektionssatz: eine Menge ist r.a. wenn sie die Projektion einer rekursiven Menge ist. Das Bild im Skript ist relativ eindeutig wenn man wei\u00df, nach was man schauen muss. Ich nehme hierzu ein konkretes Beispiel mit \\(k=1\\) und der Menge \\(B = \\{(1,4),(1,2),(3,3),(3,2),(3,1),(5,1),(6,1)\\}\\), welche aus \\(7\\) Tupeln besteht.<\/p>\n<p>Wir haben also zwei Achsen, die wir wie in der Definition \\(t\\) und \\(x\\) nennen. So sieht es dann aus:<\/p>\n<p><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/projektionssatz.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-1121\" style=\"margin-left: 150px; margin-right: 250px;\" title=\"projektionssatz\" alt=\"\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/projektionssatz-221x300.png\" width=\"221\" height=\"300\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/projektionssatz-221x300.png 221w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/projektionssatz.png 427w\" sizes=\"auto, (max-width: 221px) 100vw, 221px\" \/><\/a><\/p>\n<p>Das Bild ist angelehnt an das aus dem Skript, nur mit einer Sonne, die ich gleich erkl\u00e4re. Im Skript steht<\/p>\n<p style=\"padding-left: 30px;\"><em>&#8222;Die Projektion ist der eindimensionale Schatten bei der Beleuchtung von oben&#8220;. <\/em><\/p>\n<p>Wir machen aus unserem \\(2\\)-Tupel nun ein \\(1\\)-Tupel: Uns interessieren nur die \\(x\\)-Werte aus den Tupeln, und so kommen wir auf die 2. x-Achse im Bild f\u00fcr unser \\(A = \\{(1),(3),(5),(6)\\}\\) . Das ist unsere vorderste Front.<\/p>\n<p>Der Projektionssatz sagt also aus:<\/p>\n<blockquote><p>War unsere Menge \\(B\\) rekursiv (entscheidbar), so ist unsere Projektion \\(A\\) rekursiv aufz\u00e4hlbar (r.a.). Die Umkehrrichtung gilt auch: Ist unsere Projektion r.a., so ist die Menge \\(B\\) entscheidbar.<\/p><\/blockquote>\n<p>Aber beweisen wie diese Aussagen zun\u00e4chst:<\/p>\n<p><strong><span style=\"text-decoration: underline;\">1. Teilbeweis zu Nr. 1<\/span>:\u00a0<\/strong>\\(A\\text{ ist r.a.}\\Rightarrow{A=\\emptyset}\\) oder \\(A=Bild(g)\\) mit \\(g\\in R^{(1)}\\).<\/p>\n<p style=\"padding-left: 30px;\">Das ist umgangssprachlich am besten so auszudr\u00fccken: eine leere Menge \\(A=\\emptyset\\) ist der Definition nach immer rekursiv\/entscheidbar. Also Auch immer rekursiv aufz\u00e4hlbar\/semi-entscheidbar. Hier gibt es f\u00fcr uns nichts weiter zu beweisen.<\/p>\n<p style=\"padding-left: 30px;\">Ansonsten gilt: wenn die Menge durch eine totale Funktion aufgez\u00e4hlt werden kann, so ist diese Menge rekursiv-aufz\u00e4hlbar\/semi-entscheidbar. Das ist leicht einzusehen: Semi-Entscheidbarkeit einer Menge \\(A\\) bedeutet ja, dass f\u00fcr f\u00fcr jedes Element aus \\(A\\) immer einen positiven (oder negativen, aber nicht beides gleichzeitig) Bescheid bekommen und somit auch \\(A\\) tats\u00e4chlich die Bildmenge der Funktion ist, die sie entscheidet: n\u00e4mlich \\(g\\) ist.<\/p>\n<p style=\"padding-left: 30px;\">Haben wir z.B. die Gesamtmenge der Instanzen f\u00fcr das <a href=\"https:\/\/fernuni.digreb.net\/?p=2313\">Post&#8217;sche Korrespondenzproblem<\/a> und wollen wir daraus die Menge der l\u00f6sbaren Instanzen konstruieren, so k\u00f6nnen wir f\u00fcr jedes Element der Gesamtmenge die Funktion \\(g\\) laufen lassen, die es in jedem Fall positiv entscheidet wenn eine L\u00f6sung daf\u00fcr gefunden wurde (dass wir das k\u00f6nnen, haben wir im letzten Beitrag schon gezeigt) und somit jedes Element aus der Menge \\(A\\), der Menge der gel\u00f6sten Probleminstanzen, aufz\u00e4hlen.<\/p>\n<p style=\"padding-left: 30px;\">Genau diese Definition begr\u00fcndet den Namen Art von Mengen: sie werden von \\(g\\) aufgez\u00e4hlt und sind damit <em>rekursiv aufz\u00e4hlbar<\/em>.<\/p>\n<p style=\"padding-left: 30px;\">Das war der erste Teil. Kommen wir nun zum Umkehrschluss.<\/p>\n<p><strong><span style=\"text-decoration: underline;\">2. Teilbeweis zu Nr. 1<\/span>:\u00a0<\/strong>\\(A\\text{ ist r.a.}\\Leftarrow{A=\\emptyset}\\) oder \\(A=Bild(g)\\) mit \\(g\\in R^{(1)}\\).<\/p>\n<p style=\"padding-left: 30px;\">Fall 1: \\(A=\\emptyset\\): Wir nehmen an, dass die \\(A\\) leer ist. Nun suchen wir eine Funktion \\(d\\), die f\u00fcr alle Eingabewerte \\(n\\) kein Ergebnis liefert und setzen \\(A\\) als Definitionsmenge dieser Funktion \\(d\\): \\(A=Def(d)\\). Damit haben wir den ersten teil gezeigt.<\/p>\n<p style=\"padding-left: 30px;\">Fall 2: Nun nehmen wir eine totale Funktion \\(g\\) und setzen \\(A\\) als Bildmenge von \\(g\\): \\(A=Bild(g)\\). Jetzt kommt unser \\(f\\) ins Spiel:<\/p>\n<p style=\"padding-left: 60px;\">\\(f(y)=\\mu{x}[g(x)=y]\\)<\/p>\n<p style=\"padding-left: 30px;\">Was macht \\(f\\)? Es gibt uns f\u00fcr einen Eingabewert \\(y\\) das kleinste \\(x\\), wo gilt, dass der Funktionswert von \\(g\\) bei der Eingabe von \\(x\\) genau \\(y\\) ist.<\/p>\n<p style=\"padding-left: 30px;\">Man mache sich hier klar, dass egal, was \\(g\\) als Eingabewert bekommt, wir immer \\(div\\) zur\u00fcckbekommen (denn die leere Menge \\(A\\) ist die Bildmenge von \\(g\\)).<\/p>\n<p style=\"padding-left: 30px;\">\\(f\\) kann im Gegenzug alle Werte aus \\(\\mathbb{N}\\) bekommen und auf alle abbilden. Diese Funktion ist offensichtlich berechenbar.<\/p>\n<p style=\"padding-left: 30px;\">Das bedeutet: f\u00fcr ein \\(y\\in{Def(f)}\\) gibt es auch ein \\(x\\) mit \\(g(x)=y\\). Da \\(y\\in{Bild(g)}\\) ist, gilt: \\(Def(f)=Bild(g)\\) und \\(Bild(g)\\) ist somit rekursiv aufz\u00e4hlbar.<\/p>\n<p style=\"padding-left: 30px;\">Und das war der zweite Teil.<\/p>\n<p><strong><span style=\"text-decoration: underline;\">1. Teilbeweis zu Nr. 2<\/span>:\u00a0<\/strong>\\(A\\text{ ist r.a.}\\Rightarrow{B}\\text{ rekursiv}\\)<\/p>\n<p style=\"padding-left: 30px;\">Zeigen wir zun\u00e4chst den umgekehrten Weg von Punkt 2 mit: \\(A\\text{ ist r.a.}\\Rightarrow{B}\\text{ rekursiv}\\). Daf\u00fcr gehen wir davon aus, dass eine Menge \\(A\\subseteq\\mathbb{N}^k\\) rekursiv aufz\u00e4hlbar ist:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\">Dann gibt es eine G\u00f6delnummer \\(i\\) f\u00fcr ein \\(x\\in{A}\\) mit \\(\\varphi_i(\\pi^{(k)}(x))\\) existiert.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Es gibt also eine Maschine mit der Nr. \\(i\\), die uns zum Element \\(x\\) eine Ausgabe beschert. Die <a title=\"TI: Cantorsche Tupelfunktion (Update: Umkehrfunktion)\" href=\"https:\/\/fernuni.digreb.net\/?p=580\">Cantorsche Tupelfunktion<\/a> \\(\\pi\\) ist hier nur dazu da um eine evtl. Mehrstelligkeit \\(k\\) der Eingabe f\u00fcr die Maschine\u00a0auf eine Stelle herunterzurechnen.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\">Gibt es die Maschine mit der Nr. \\(i\\), so gibt es auch selbstverst\u00e4ndlich die dazu geh\u00f6rige\u00a0<a title=\"TIA: Standardnummerierung und -Komplexit\u00e4t Phi und das Phi-Theorem (Lernziele KE5, 1\/3, Update)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">Schrittzahlfunktion<\/a> \\(SZ\\), die im \\(\\Phi\\)-Theorem benutzt wird: \\(\\Phi_i(\\pi^{(k)}(x))\\)<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Kennen wir alles schon: das ist die Anzahl der Schritte, die \\(\\varphi_i\\) bei der Eingabe von \\(x\\) braucht um zum Ende zu gelangen. Da die Menge \\(A\\) rekursiv aufz\u00e4hlbar ist, existiert f\u00fcr jedes \\(x\\in{A}\\) diese Rechenzeitfunktion \\(\\Phi_i(x)\\).<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\">Und damit gilt: \\((\\exists{t})\\Phi_i(\\pi^{(k)}(x))\\leq{t}\\)<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Es gibt also ein kleinstes \\(t\\), d.h. die minimale Anzahl der Schritte, die die Maschine \\(\\varphi_i\\) bei der Eingabe von \\(x\\) rechnet um bis zum Ergebnis zu gelangen. Es gibt aber auch noch mehr \\(t&#8217;s\\). Eben die, die kleiner sind als die maximale Schrittzahl, die die Maschine bei der Eingabe von \\(x\\) rechnet um bis zur HALT-Marke zu gelangen.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\">Nun definieren wir die Menge \\(B=\\{(x,t)\\mid\\Phi_i(\\pi^{(k)}(x))\\leq{t}\\}\\)<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Die Paare sind also die Eingabe \\(x\\) f\u00fcr die Maschine \\(\\varphi_i\\)\u00a0und \\(t\\) die Anzahl der Schritte, die die Maschine bis zum Ergebnis rechnen k\u00f6nnte. Sagen wir z.B. die Maschine rechnet bei der Eingabe von \\(x\\) genau \\(5\\) Schritte bis sie an der \\(HALT\\)-Marke ankommt, so kann \\(t\\leq{5}\\) sein. In der Menge \\(B\\) w\u00fcrde daher \\((x,1)(x,2)(x,3),(x,4),(x,5)\\) liegen.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\">Nach dem \\(\\Phi\\)-Theorem ist diese Menge \\(B\\) also entscheidbar.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Das sollte klar sein: das Paar \\((x,t)\\), also die Eingabe \\(x\\) und die Rechenzeit\u00a0\\(t\\) ist entscheidbar, da wir f\u00fcr jedes \\(x\\) (wenn es in der Menge \\(A\\) ist) immer einen Ausgabewert haben, ist auch die maximale Schrittzahl immer gegeben. Wir k\u00f6nnen entscheiden ob die Maschine bei der Eingabe von \\(x\\) nach \\(t\\) Schritten h\u00e4lt oder nicht.<\/p>\n<p style=\"padding-left: 30px;\">Anders ausgedr\u00fcckt: Wir k\u00f6nnen fragen: &#8222;Hey, gilt \\((x,5)?\\) und \\(\\Phi\\) pr\u00fcft ab ob bei der Eingabe von \\(x\\) die Maschine innerhalb von \\(5\\) Schritten zum Ergebnis kommt und kann dann sagen &#8222;Ja, das geht!&#8220; oder &#8222;Nein, ging nicht!&#8220;. Diese Menge ist also Entscheidbar.<\/p>\n<p style=\"padding-left: 30px;\">Der eine Weg von Punkt 2 ist damit gezeigt.<\/p>\n<p><strong><span style=\"text-decoration: underline;\">2. Teilbeweis zu Nr. 2<\/span>:\u00a0<\/strong>\\({A}\\text{ ist r.a.}\\Leftarrow{B}\\text{ rekursiv}\\)<\/p>\n<p style=\"padding-left: 30px;\">Und nun die andere Richtung:\u00a0\\({A}\\text{ ist r.a.}\\Leftarrow{B}\\text{ rekursiv}\\). Sei \\(B\\subseteq\\mathbb{N}^{k+1}\\) also rekursiv\/entscheidbar.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\"><span style=\"line-height: 13px;\">Setzen wir die Menge \\(A=\\{x\\in\\mathbb{N}^k\\mid{}(\\exists{t} (x,t)\\in{B}\\}\\)<\/span><\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\"><span style=\"line-height: 13px;\"><span><br \/>\n\\(B\\) ist, wie wir wissen ja entscheidbar. Zu einer Eingabe erhalten wir (wenn sie zu einer r.a. Menge geh\u00f6rt) auch eine maximale Rechenzeit und k\u00f6nnen so pr\u00fcfen ob sie \\(t\\) entspricht oder gr\u00f6\u00dfer\/kleiner ist. Hier ist \\(A\\) also\u00a0die Menge der Eingaben, d.h. die ersten Elemente aus den Tupeln von \\(B\\), die aus Eingabe \\(x\\) und zugeh\u00f6rigem Wert f\u00fcr eine angenommene Rechenzeit \\(t\\) bestehen.<\/span><\/span><\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li style=\"padding-left: 30px;\">Nun definieren wir unsere &#8222;Projektionsfunktion&#8220; durch<\/li>\n<\/ul>\n<p style=\"padding-left: 60px;\">\\(f(x):=\\mu{t}[cf_B(x,t)=1]\\)<\/p>\n<p style=\"padding-left: 30px;\">Was tut \\(f\\)? Zun\u00e4chst fragen wir uns, was tut \\(cf_B\\)? Das ist die (volle) charakteristische Funktion f\u00fcr die Menge \\(B\\). Sie gibt uns eine \\(1\\) zur\u00fcck wenn die Maschine bei der Eingabe von \\(x\\) nach maximal \\(t\\) Schritten h\u00e4lt.<br \/>\nUnd \\(\\mu{t}\\)? Sie gibt uns das kleinste \\(t\\) zur\u00fcck, d.h. die minimalste Anzahl an Schritten, die ben\u00f6tigt werden um bei der Eingabe von \\(x\\) von der Maschine eine Ausgabe zu erhalten, denn in unserer menge \\(B\\) liegen ja durchaus mehrere Kombinationen von \\((x,t)\\) mit den unterschiedlichsten \\(t&#8217;s\\).<\/p>\n<p style=\"padding-left: 30px;\">Mit \\(f(x)\\) bekommen wir das also f\u00fcr die Eingabe \\(x\\) kleinste \\(t\\).<\/p>\n<p style=\"padding-left: 30px;\">Der Definitionsbereich von \\(f\\) sind somit alle Elemente aus \\(A\\) und \\(A\\) damit rekursiv aufz\u00e4hlbar.<\/p>\n<p>Done.<\/p>\n<p><strong>Exkurs<\/strong>: den\u00a0<a href=\"http:\/\/ccc.cs.uni-duesseldorf.de\/~rothe\/INFO4\/folien-kapitel-10.pdf\">Unterlagen der Uni D\u00fcsseldorf<\/a>\u00a0kann man den Projektionssatz auch mit einer anderen Menge \\(B\\) beweisen, z.B. mit \\((x,z)\\) (wobei \\(x\\) die Eingabe und \\(z=\\pi(y,t)\\) das durch die Tupelfunktion \\(\\pi\\) auf ein Element \\(z\\) zur\u00fcckgef\u00fchrte Paar aus Ausgabe \\(y\\) und Schrittzahl \\(t\\) ist) wenn \\(T_i(x,t)\\) (auch Turingpr\u00e4dikat genannt) erf\u00fcllt ist.<\/p>\n<p>Das Turingpr\u00e4dikat ist genau dann erf\u00fcllt wenn Maschine \\(T_i\\) bei der Eingabe von \\(x\\) nach \\(t\\) Schritten mit einer Ausgabe \\(y\\) h\u00e4lt.<\/p>\n<p>Im Endeffekt also nur ein kleines Upgrade unserer Menge \\(B\\).<\/p>\n<p>Fassen wir die Ergebnisse zusammen, kommen wir so zu unserer Antwort zum Lernziel.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Der erste Teil des Projektionssatzes ist der Grund f\u00fcr den Begriff \u00a0&#8222;rekursiv-aufz\u00e4hlbar&#8220; f\u00fcr eine Menge \\(A\\). Diese ist genau dann rekursiv-aufz\u00e4hlbar wenn ihre Elemente von einer totalen Funktion \\(g\\) aufgez\u00e4hlt werden k\u00f6nnen, es gilt damit \\(A=Bild(g)\\) und \\(A\\) ist r.a.<\/p>\n<p>Der zweite Teil ist die Projektion, die aus den Eingabewerten \\(x\\) einer r.a. Menge \\(A\\) besteht. Da diese positiv beschieden sind, gibt es auch die zugeh\u00f6rige Anzahl an Schritten, die die Maschine f\u00fcr den positiven Bescheid brauchte. Setzen wir in den Tupeln \\((x,t)\\) das Element \\(t\\) auf Werte, die h\u00f6her sind als die Schrittzahlfunktion der Maschine bei der Eingabe \\(x\\), so haben wir in der Menge \\(B\\) mehrere Tupel der Form \\((x,t)\\) mit festem \\(x\\) und variablem \\(t\\).<\/p>\n<p>Aus diesen Elementen der Menge \\(B\\) bilden wir die \\(x\\)&#8211; und \\(y\\)-Achse unserer Grafik. Diese Wertekombinationen aus \\(x\\) und \\(t\\) sind entscheidbar (ich kann entscheiden ob ich zu einer positiven Eingabe \\(x\\) mehr als \\(t\\) Schritte brauche oder nicht). Das ist der Weg von einer rekursiv-aufz\u00e4hlbaren Menge \\(A\\) zu einer entscheidbaren \\(B\\).<\/p>\n<p>Auch der R\u00fcckweg gilt: aus der Menge \\(B\\) mit den Elementen \\((x,t)\\) kann ich mir meine Eingabewerte \\(x\\) wieder rausholen, indem ich mich nur f\u00fcr das kleinste \\(t\\) interessiere (die Minimierungsfunktion). Damit &#8222;blende&#8220; ich alle anderen Kombinationen mit gr\u00f6\u00dferem \\(t\\) einfach aus. Das ist die Projektion.<\/p>\n<p>Merksatz: Eine Menge ist rekursiv aufz\u00e4hlbar wenn sie die Projektion einer entscheidbaren Menge ist.<\/p>\n<p>Weiter geht es im n\u00e4chsten Beitrag zum <a href=\"https:\/\/fernuni.digreb.net\/?p=1117\">Halte- \u00c4quivalenz- und Korrektheitsproblem, Reduzierbarkeit und Satz von Rice<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: Schnitzer im Projektionssatz aufgefallen. Fixed. Als ich die letzten Beitr\u00e4ge zu Kurseinheit 5 von TIA durchgegangen bin, ist mir aufgefallen, dass einige Beweise doch noch nicht so nachvollziehbar sind, wie ich das gerne h\u00e4tte. Nach dem Editieren kam ich auf eine Seitenzahl von \u00fcber 20. Schon wieder. Da blieb mir also nichts anderes \u00fcbrig, &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=2368\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: Bild- und Projektionssatz (Lernziele KE6 2\/4, Update)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-2368","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2368","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2368"}],"version-history":[{"count":15,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2368\/revisions"}],"predecessor-version":[{"id":3507,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2368\/revisions\/3507"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}