Satz Von Rice Beispiel

Https Www Tu Ilmenau De Fileadmin Public Iti Lehre Buk Ws10 11 Buk Vorlesung 09 Pdf

Es ist l 17 l s f ur s ff m jf m bin 17 bin 42 g.

Satz von rice beispiel. Ist h 17 entscheidbar. N n mit χ a x 1 fallsx a 0 fallsx a berechenbarist. Aist genau dann entscheidbar wenn die charakteristische funktionχ a. Benannt wurde der satz nach henry gordon rice der ihn 1953 veröffentlichte 1 er besagt dass es unmöglich ist eine beliebige nicht triviale eigenschaft der erzeugten funktion einer turing maschine algorithmisch zu entscheiden.

Sei l 17 fhmijm berechnet bei eingabe der zahl 17 die zahl 42g. Sei h 17 fhmijauf jeder eingabe stoppt m nach 17 schritteng. B es sei a n gegeben. Uber diese sprache sagt der satz von rice nichts aus.

Es ist l 17 l s f ur s ff m jf m bin 17 bin 42 g. Unentscheidbarkeit satz von rice beweis. Satz von rice weitere anwendungsbeispiele beispiel 3. Da s r gilt gibt es eine funktion q r s.

Aus dem satz von rice folgt beispielsweise dass es keinen algorithmus gibt der für jede turing maschine entscheidet ob sie für jede eingabe hält oder nicht. Es ist l 17 l s f ur s ff m jf m bin 17 bin 42 g. Somit ist diese sprache gem aˇ dem satz von rice nicht entscheidbar. Ist h 17 entscheidbar.

Wir ordnen nun jedem wort w 0 1 eine turing maschine m w zu die sich bei einer eingabe y 0 1 wie folgt verh alt. Ist h 17 entscheidbar. Sei h 17 fhmijauf jeder eingabe stoppt m nach 17 schritteng. Sei q eine turing maschine die q berechnet.

C wenn eine menge a n entscheidbar ist dann ist auch ihr komplement n a. Uber diese sprache sagt der satz von rice nichts aus. S r displaystyle mathcal s mathcal r ist hierbei die menge aller total berechenbaren funktionen. Uber diese sprache sagt der satz von rice nichts aus.

Der satz von rice ist ein ergebnis der theoretischen informatik. Sei l 17 fhmijm berechnet bei eingabe der zahl 17 die zahl 42g. 1 m w ignoriert die eingabe y zun achst und simuliert mw auf dem leeren band. Satz von rice weitere anwendungsbeispiele beispiel 3.

Der satz von rice wirbenötigendiefolgendenaussagen. Somit ist diese sprache gem aˇ dem satz von rice nicht entscheidbar. Sei l 17 fhmijm berechnet bei eingabe der zahl 17 die zahl 42g.

Source : pinterest.com