Die Mathe-Redaktion - 22.10.2019 16:24 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
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 775 Gäste und 20 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Sind die Fragen entscheidbar?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Sind die Fragen entscheidbar?
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1392
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-11


Hallo,

ich gucke folgende Aufgabe:

Sind die folgenden Fragen entscheidbar? Geben Sie einen entsprechenden Algorithmus an oder zeigen Sie mit Hilfe des Satzes von Rice, daß das Problem unentscheidbar ist.
(a) Hält ein beliebiger Algorithmus bei jeder Eingabe ungerader Länge?
(b) Hält eine beliebige Turingmaschine auf allen Eingaben kleiner oder gleich 1000 innerhalb der ersten 1000 Schritte?
(c) Gibt ein beliebiger Algorithmus bei geeigneter Eingabe eine Zahl aus, die als String interpretiert ein Palindrom ist?
(d) Liefert ein beliebiger Algorithmus, der für wenigstens eine Eingabe nicht hält, jede natürliche Zahl als Ausgabewert?


Ich habe folgendes gemacht:

(a) Sei $\phi$ die Funktion die von ein Algorithmus berechnet wird.

Da der Algorithmus bei jeder Eingabe ungerader Länge hält haben wir dass die Elemente der Form $2n+1$ im Definitionsbereich der Funktion $\phi$ liegen, das $\phi(2n+1)$ ist also für alle $n\in \mathbb{N}_0$ definiert.

Wir betrachten die daher die Menge $M_1=\{i\in \mathbb{N}_0\mid \text{ Für alle } n\in \mathbb{N}_0 \text{ ist } \phi_i(2n+1) \text{ definiert }\}$.

Seien $i,j\in \mathbb{N}_0$ mit $i\in M_1$ und $\phi_i=\phi_j$.

Wenn $i\in M_1$ dann haben wir dass $\phi_i(2n+1)$ definiert ist.

Da $\phi_i = \phi_j$ folgt es dass $\phi_i (2n+1)= \phi_j (2n+1)$ für alle $n\in \mathbb{N}_0$. Da $\phi_i(2n+1)$ für alle $n\in \mathbb{N}_0$ definiert ist, folgt es dass $\phi_j(2n+1)$ auch für alle $n\in \mathbb{N}_0$ definiert ist. Davon folgt es dass $j\in M_1$.

Das bedeutet dass $M_1$ Funktionen respektiert.

Nach dem Satz von Rice ist $M_1$ also genau dann entscheidbar, wenn $M_1 = \emptyset$ oder $M_1 = \mathbb{N}_0$ gilt.

Es gibt Indizes $i,j \in \mathbb{N}$ mit $\phi_i(n) = 0$ und $\phi_j(n) = n$ für alle $n \in \mathbb{N}_0$, also gelten $i \in M_1$ (und damit $M_1 \neq \emptyset$) sowie $j \notin M_1$ (und damit $M_1 \neq \mathbb{N}_0$). Das heißt, $M_1$ ist nach dem Satz von Rice nicht entscheidbar.


(b) Es ist entscheidbar, ob eine deterministische Turing-Maschine für irgendeine Eingabe kleiner oder gleich $1000$ innerhalb der ersten $1000$ Schritt hält.

Wir führen die Turing-Maschine nacheinander auf allen Wörtern $w \in \Sigma^{\star}$ mit $w \leq 1000$ für höchstens $1000$ Schritte aus.

Wenn wir höchstens $1000$ Schritte simuliert haben, halten wir und geben “ja” aus, ansonsten halten wir, sobald wir die Turing-Maschine auf allen Wörtern <math>w</math> simuliert haben, und geben “nein” aus.  
 

(c) Es ist entscheidbar, ob eine Ausgabe Palindrom ist oder nicht.
 
 
(d) Wir wenden den Satz von Rice an:

Sei $\phi$ die Funktion die von ein Algorithmus berechnet wird.

Wir betrachten die die Menge $M_2=\{i\in \mathbb{N}_0\mid \text{ Für alle } n\in \mathbb{N}_0 \text{ ist } \phi_i(n) \text{ definiert }\}$.  

Es gibt Indizes $i,j \in \mathbb{N}$ mit $\phi_i(n) = n\in \mathbb{N}_0$ und $\phi_j(m) \neq m\in \mathbb{N}_0$, also gelten $i \in M_2$ (und damit $M_2 \neq \emptyset$) sowie $j \notin M_2$ (und damit $M_2 \neq \mathbb{N}_0$). Das heißt, $M_2$ ist nach dem Satz von Rice nicht entscheidbar.



Ist alles richtig? Könnte ich etwas verbessern?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5174
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-11


Hallo mathletic,

die Antwort auf alle Fragen lautet nein. Aber vermutlich wolltest du etwas ganz anderes fragen.

2019-07-11 19:24 - mathletic im Themenstart schreibt:
(a) Hält ein beliebiger Algorithmus bei jeder Eingabe ungerader Länge?
(b) Hält eine beliebige Turingmaschine auf allen Eingaben kleiner oder gleich 1000 innerhalb der ersten 1000 Schritte?
(c) Gibt ein beliebiger Algorithmus bei geeigneter Eingabe eine Zahl aus, die als String interpretiert ein Palindrom ist?
(d) Liefert ein beliebiger Algorithmus, der für wenigstens eine Eingabe nicht hält, jede natürliche Zahl als Ausgabewert?

Etwa bei (a): Finde einen Algorithmus, der unabhängig von der Eingabe nie endet.



  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1392
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2019-07-11


Was genau meinst du? Ist die Formulierung der Fragen falsch?



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5174
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-07-11


2019-07-11 21:58 - mathletic in Beitrag No. 2 schreibt:
Was genau meinst du? Ist die Formulierung der Fragen falsch?

So ist es. Was verstehst du unter einem "beliebigen"? Was für ein beliebiges x gilt, gilt nach allgemeinem Sprachgebrauch jedes x.

Wie lautet denn der originale Wortlaut der Aufgabe?



  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1392
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2019-07-11


2019-07-11 22:06 - StrgAltEntf in Beitrag No. 3 schreibt:
2019-07-11 21:58 - mathletic in Beitrag No. 2 schreibt:
Was genau meinst du? Ist die Formulierung der Fragen falsch?

So ist es. Was verstehst du unter einem "beliebigen"? Was für ein beliebiges x gilt, gilt nach allgemeinem Sprachgebrauch jedes x.

Wie lautet denn der originale Wortlaut der Aufgabe?

Das ist die Originalaufgabe.



Also so wie diese formuliert sind kann man nicht bestimmen ob diese entscheidbar sind oder nicht?



  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1392
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-07-13


(c) Um den Satz von Rice anzuwenden muss man eine Funktion finden die eine palindrome Ausgabe hat und eine Funktion die keine palindrome Ausgabe hat, um eine nicht-triviale Eigenschaft zu bekommen?


(d) Um den Satz von Rice anzuwenden:

Sei $\phi$ die Funktion die vom Algorithmus berechnet wird. Wir betrachten die Menge $M=\{i\in \mathbb{N}_0 \mid \text{ Für alle } n\in \mathbb{N}_0 \ \text{ ist } \phi_i(n) \ \text{ definiert }\}$, oder nicht?  

Seien $i,j \in \mathbb{N}_0$ mit $\phi_i = n$ für eine natürliche Zahl $n\in \mathbb{N}$ und $\phi_j\neq m\in \mathbb{N}$ (da der Algorithmus für wenigstens eine Eingabe nicht hält).

Dann $i \in M$ und $j \notin M$, also $M\neq \emptyset$ und $M\neq \mathbb{N}_0$, und jetzt kann man den Satz von Rice anwenden.



Ist alles richtig?



  Profil  Quote  Link auf diesen Beitrag Link
mathletic hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    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-2019 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]