Die Mathe-Redaktion - 19.07.2018 18:56 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind Gäste und Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Entscheidbarkeit
Druckversion
Druckversion
Autor
Universität/Hochschule J Entscheidbarkeit
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-06-17

\(\begingroup\)
Hallo :),

und zwar soll ich folgende Aussage beweisen oder wiederlegen:

Wenn $L \subseteq Σ^*$ ein entscheidbares Problem und $f : \Sigma^∗
\to \Gamma^∗$ eine berechenbare partielle Funktion ist, dann ist $f (L)\subseteq  \Gamma^∗$ entscheidbar.

Vom Gefühl her denke ich das die Aussage nicht stimmt. Jedoch bin ich mir beim Beweis unsicher.

Für einen Hinweis wäre ich dankbar.

Viele Grüße
Finis86
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-06-18

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Wo kommt denn dein Gefühl her?
Wenn du meinst, die Aussage gelte nicht, dann gib eine Belegung für $\Gamma,\Sigma,f,L$ an, mit der sie falsch ist. Fange bei der Suche mit den einfachsten Kombinationen an, und nutze aus, dass $f$ partiell sein darf.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-06-18

\(\begingroup\)
Ich hatte mit überlegt, dass die charakteristische Funktion dann die Gestalt hat
$\chi_{f(L)}(w)=\left\{\begin{array}{l l}
1& \text{falls } w\in f(L)\\
0 & sonst
\end{array}
\text{ für alle } w\in \Gamma^*\right.$
Das würde bedeuten, dass:
$\chi_{f(L)}(w)=\left\{\begin{array}{l l}
1& \text{falls }f^{-1}( w)\in L\\
0 & sonst
\end{array}
\text{ für alle } w\in \Gamma^*\right.$
Nun existiert die Umkehrfunktion ja nicht für alle partiellen Funktionen. Mit fällt eben nur leider kein Gegenbeispiel ein. Kann aber auch sein das dieser Gedankengang nicht zielführend ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-06-18


2018-06-18 19:02 - Finis86 in Beitrag No. 2 schreibt:
[...] Kann aber auch sein das dieser Gedankengang nicht zielführend ist.
Er ist mit ziemlicher Sicherheit nicht zielführend.



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-06-18

\(\begingroup\)
Das hilft mir leider nicht viel weiter. Wenn f partiell ist heißt das dass nicht alle $w\in \Gamma^*$ getroffen werden. Ich denke halt nicht das wenn ein Wert f(L) undef annimmt, das dann $\chi_{f(L)}$ berechenbar ist.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-06-18

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Wie schon gesagt: um zu zeigen, dass die Aussage nicht gilt, kannst du selber ein ganz konkretes f (etc.) angeben, das die Annahme, die Aussage gelte für alle Gamma, Sigma, f, L, auf einen Widerspruch führt.
Und wie gesagt: fange mit trivialen Dingen an. Um nicht gleich alles zu verraten: fällt dir eine partielle Funktion $f\colon \IN \to \IN$ ein, die einen nicht entscheidbaren Definitions- und/oder Wertebereich hat?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-06-18

\(\begingroup\)
Das ist ja gerade mein Problem, darüber denke ich schon eine Weile nach. Wir hatten als partielle Funktion z.B. die Wurzelfunktion also:
$\sqrt{\cdot}:\mathbb{N}\to \mathbb{N}$ diese Funktion ist berechenbar, weil $\mu$-rekursiv.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-06-18


Der Definitionsbereich der Wurzelfunktion wäre aber entscheidbar. Sagt dir der Begriff „universelle Funktion“ etwas?



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-06-18


Nicht wirklich um ehrlich zu sein.



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-06-18


Hmm, okay. Hast du denn irgendein Beispiel für ein nicht entscheidbares Problem?



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2018-06-18


In der Vorlesung wurde gezeigt: Das spezielle Halteproblem ist nicht entscheidbar.



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-06-18


Wurde auch gezeigt (oder zumindest erwähnt), dass das spezielle Halteproblem halbentscheidbar ist?



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2018-06-18


Nein das wurde nicht erwähnt.



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-06-18


Es ist jedenfalls so. Versuche mal, mit der Information eine Lösung zu basteln. Wenn du die hast, kannst du ja wahrscheinlich hinterher etwas verwandtes ableiten, das dem Aufgabensteller genehm ist.



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2018-06-18


Also wenn das spezielle Halteproblem halbentscheidbar ist, dann ist die halbe charakteristische Funktion berechenbar. Für jedes entscheidbare Problem existiert eine deterministische Turingmaschine, gibt man die Codierung dieser in die halbe charakteristische Funktion, erhält man das spezielle Halteproblem, das ist ja nicht entscheidbar. So was in der Richtung?



  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-06-18

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Nein, so funktioniert das nicht. Wenn du den Code einer TM, die eine totale Funktion realisiert, an die halbe charakteristische Funktion schickst, geschieht nichts interessantes -- man erhält einfach das Ergebnis.

Noch ein Tipp und etwas Präzision: Da das spezielle Halteproblem $H\subseteq \Sigma^*$ halbentscheidbar ist, haben wir eine partielle berechenbare Funktion $h\colon \Sigma^* \to \emptyset^*$ mit $$h(\alpha)=\begin{cases} \varepsilon & \alpha \in H \\ \mathsf{undefiniert}&\text{sonst}\end{cases}$$
(es ist also $\mathsf{dom}(h)=H$).
Wir können jetzt die Definition von $h$ so verändern, dass ein interessanteres $f\colon \Sigma^* \to \Sigma^*$ herauskommt, das immer noch berechenbar ist, und für das gilt $f(\Sigma^*) = H$. Wie? Warum ist das Ergebnis berechenbar? Und wie hilft das beim vorliegenden Problem?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2018-06-19

\(\begingroup\)
Also wenn man die Funktion folgendermaßen abändert:
$f(\alpha)=\left\{\begin{array}{l l}
\alpha& \text{falls } \alpha\in H\\
undef & sonst
\end{array}\right.$
dann ist $f(\Sigma^*)=H$
Das ist berechnenbar, da für h da ein äquivalentes WHILE-Programm $P_h$ existiert. Ändert man das folgendermaßen als $P_f$ab
$x_{n+1}=x_1$
$P_h$
$IF(x_1=\varepsilon)\{$
$x_1=x_{n+1}\}$

Dann ist f berechenbar. Jetzt hat man eine Funktion deren Wertebereich gleich dem Halteproblem ist. Dieses ist nur halb entscheidbar.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-06-19

\(\begingroup\) \(\newcommand{\sem}[1]{[\![#1]\!]}\newcommand{\name}[1]{\ulcorner#1\urcorner}\)
Gut. Das IF im Pseudocode kannst du eigentlich weglassen, da h so definiert ist, dass $P_h$ in den Fällen, in denen das Argument nicht in H ist, schon nicht terminiert.
Wie musst du nun also genau $\Gamma, L$ und $f$ wählen, um die Aussage in #0 zu widerlegen?
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, vom Themenstarter, eingetragen 2018-06-19

\(\begingroup\)
Also für f würde ich die eben konstruierte Funktion wählen. Dem entsprechend müssen ja auch $\Gamma$ und $\Sigma$ gewählt werden. Also die halbe charakteristische Funktion des speziellen Halteproblems ist laut unserer Vorlesung eine Funktion von $\{0,1\}^* \to \{0,1\}$. Die modifizierte Funktion hat ja die gleiche Eingabe also $\Sigma^*=\{0,1\}^*$ und $\Gamma=\{0,1\}^*$, da ja die Eingabe wieder ausgegeben wird falls $f(\alpha)\in \Gamma^*$. $\{0,1\}^*$ ist ja entscheidbar. Also müsste das doch so passen.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2018-06-19


Das stimmt noch nicht ganz (aber fast). Außerdem hast du nicht explizit gesagt, was L ist.



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, vom Themenstarter, eingetragen 2018-06-19

\(\begingroup\)
Also L ist dann ja das Problem $\Sigma^*$ mit $\Sigma=\{0,1\}$, denn ein Problem ist eine Teilmenge von $\Sigma^*$ kann also auch $\Sigma^*$ sein und das ist entscheidbar.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, vom Themenstarter, eingetragen 2018-06-19

\(\begingroup\)
Und bei dem $\Gamma^*$ hat sich ein Fehler eingeschlichen, es sollte heißen $\Gamma^*=\{0,1\}^*$
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1259
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2018-06-19


Okay.



  Profil  Quote  Link auf diesen Beitrag Link
Finis86
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 17.12.2016
Mitteilungen: 29
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, vom Themenstarter, eingetragen 2018-06-19


Vielen Dank für die Hilfe.



  Profil  Quote  Link auf diesen Beitrag Link
Finis86 hat die Antworten auf ihre/seine Frage gesehen.
Finis86 hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]