www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Komplexität & Berechenbarkeit" - bereche. partieller Funktionen
bereche. partieller Funktionen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

bereche. partieller Funktionen: Problem
Status: (Frage) beantwortet Status 
Datum: 12:18 Mi 07.12.2005
Autor: Flugzwerg

Halli Hallo!

Ich habe da ein Problem mit der folgenden Aufgabe:


Zeigen Sie das die partielle funktion


$f: A [mm] \subseteq \IN \to \IN$ [/mm]


berechenbar ist.


[mm]f\left(n\right) := \begin{cases}\varphi_n \left(n\right)+1, & \mbox{für } n \in \mathrm{Def}\left(\varphi_n\right) \mbox{} \\ \mathrm{div}, & \mbox{für } n \notin \mathrm{Def}(\varphi_n) \mbox{} \end{cases}[/mm]


Die beiden geschweiften Klammern sollen eine grosse darstellen.

So.

Als erstes verstehe ich nicht was ich da machen muss. Irgendwie ist die Definition schon unklar.

Also eine Teilmenge von [mm] $\IN$ [/mm] abgebildet auf [mm] $\IN$ [/mm]

für die [mm] $\varphi_n(n)+1$ [/mm] ist falls $n [mm] \in \mathrm{Def}\left(\varphi_n\right)$. [/mm]

Erste Frage:  Was ist denn hier mein Def?  Das hier ?:
$A [mm] \subseteq \IN \to \IN$ [/mm]

Und was ist [mm] $\varphi_n$? [/mm]


Wenn $n [mm] \notin \mathrm{Def}\left(\varphi_n\right)$ [/mm] dann ist es div.

Aber wie zeige ich das?
das es berechenbar oder nicht berechenbar ist???

Ich finde absolut keinen Ansatz.


Vielen Dank,

NIK





        
Bezug
bereche. partieller Funktionen: Vermutung
Status: (Antwort) fertig Status 
Datum: 10:45 Do 08.12.2005
Autor: mathiash

Hallo,

bei der Funktion  [mm] \varphi [/mm] handelt es sich vermutlich um eine universelle Funktion fuer die
Klasse der [mm] $\mu$-rekursiven [/mm] Funktionen, dafuer wird das Symbol zumindest typischerweise
in dem Kontext verwendet. Es ist also [mm] \varphi_n(x)=\varphi(n,x) [/mm] die n-te [mm] $\mu$-rekursive [/mm] Funktion
(die Numerierung ist dann nachweislich nicht injektiv).

Dann ist die Aufgabenstellung vermutlich so zu verstehen, dass gezeigt werden soll,
dass auch die Funktion

[mm] f(n)=\begin{cases}\varphi(n,n)+1 & \mbox{ für} \ \varphi(n,n) \ \mbox{definiert}\\ undef & \mbox{sonst}\end{cases} [/mm]


[mm] $\mu$-rekursiv [/mm] ist (man koennte auf den ersten Blick das Gegenteil vermuten, da ja zur
Definition fon f die universelle Funktion (man sagt auch: Goedel-Numerierung) der
mu-rek. Funktionen verwendet wird.

Intuitiv ist es klar, dass f [mm] $\mu$-rekursiv [/mm] ist, da es sich um eine berechenbare (implementierbare) Berechnungsvorschrift handelt. Formal entsteht f aus der Funktion [mm] \varphi [/mm] (die vorher als [mm] $\mu$-rekursiv [/mm] nachgewiese wurde), der Addition und der konstanten
Funktion  x |-> 1  durch Einsetzung.

Der Definitionsbereich von f ist nach Definition genau der von n -> [mm] \varphi(n,n), [/mm]
also die Menge K, die als Halteproblem bekannt ist.

Viele Gruesse,

Mathias



Bezug
                
Bezug
bereche. partieller Funktionen: noch nicht ganz klar
Status: (Frage) beantwortet Status 
Datum: 11:35 Do 08.12.2005
Autor: Flugzwerg

Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

Hallo Matiash!

Erst einmal Danke für Deine schnelle Antwort!
Leider ist unser Skript etwas kompliziert.
Die Goedel sache hab ich mir ebend angekuckt und es scheint plausibel.
Ich weiss jedoch immer noch nicht wie ich zeigen kann das es berechenbar ist. Das es berechenbar ist ist zwar klar, aber wie zeig ich das.

Inzwischen habe ich auch herausgefunden das mit phi die Standardnummerierung  phi gemeint ist.
Gezeitg werden kann es wohl mit dem  utm Theorem und folgendem Lemma:

Die wie folgt definierte Funktion h : \IN^3 \to \IN ist berechenbar.

                 1 + phi klein i (n)            falls  Standardkomplexität (groß phi ist                                das )                 (n) existiert   und groß phi i(n) <= t


h(i,n,t)= {

                0       sonst.



Ich verstehe einfach nicht wie ich mit den Sachen zeigen kann das f berechenbar ist.

Bezug
                        
Bezug
bereche. partieller Funktionen: Antwort
Status: (Antwort) fertig Status 
Datum: 12:34 Do 08.12.2005
Autor: mathiash

Hallo nochmal,

zu Deiner Nachfrage: Es sollte doch klar sein, dass, wenn die Funktion [mm] \phi \mu-rekursiv [/mm]
ist, dann auch die Funktion f [mm] \mu-rekursiv [/mm] ist (man sagt auch: berechenbar), denn sie
entsteht dann ja aus bereits als [mm] \mu-rekursiv [/mm] nachgewiesenen Funktionen durch
Einsetzen (Substitution).

Dann kann doch eigentlich fuer Dich nur noch unklar sein, warum die Funktion [mm] \phi [/mm]
[mm] \mu-rekursiv [/mm] ist, oder genauer: warum es eine [mm] \mu-rekursive [/mm] Funktion [mm] \phi [/mm] gibt, so dass
die Menge der Funktionen [mm] \phi_n,n\in \IN [/mm] genau die Menge [mm] F_{\mu} [/mm] der [mm] \mu [/mm] - rekursiven
Funktionen ist.

Dies ist sozusagen Vorgeschichte zu der von Dir beschriebenen Aufgabenstellung.
Die Konstruktion einer solchen Funktion [mm] \phi [/mm] beruht darauf, [mm] \mu [/mm] - rekursive Funktionen
durch natuerliche Zahlen zu kodieren (''Goedelisierung''). Im Detail findet man die
Konstruktion einer solchen Funktion  in jedem Buch ueber Berechenbarkeit. Die Kodierung wird entlang des Aufbaus von  [mm] F_{\mu} [/mm] definiert: Die Grundfunktionen kodiert
man durch feste kleine Zahlen, Substitution  etc. durch Tupel der Kodierungen der beteiligten Funktionen und einer festen Zahl fuer den Substitutionsoperator etc.

Dann muss man bei der Definition von [mm] \phi [/mm] nur darauf achten, dass diese Kodierungen
wieder richtig interpretiert werden.

Vielleicht ist Dir einfach nicht klar, was Berechenbarkeit heisst: Es ist  -fuer Funktione-
lediglich ein Synonym fuer [mm] \mu-Rekursivitaet. [/mm]

Hilft das weiter ?

Viele Gruesse,

Mathias

Bezug
        
Bezug
bereche. partieller Funktionen: Vermutung
Status: (Antwort) fertig Status 
Datum: 12:12 Do 08.12.2005
Autor: mathiash

Hallo,

bei der Funktion  phi handelt es sich vermutlich um eine universelle Funktion fuer die
Klasse der mu-rekursiven Funktionen, dafuer wird das Symbol zumindest typischerweise
in dem Kontext verwendet. Es ist also [mm] phi_n(x)=phi(n,x) [/mm] die n-te mu-rekursive Funktion
(die Numerierung ist dann nachweislich nicht injektiv).

Dann ist die Aufgabenstellung vermutlich so zu verstehen, dass gezeigt werden soll,
dass auch die Funktion

   f(n)  =  [mm] \begin{cases} phi(n,n) +1 & \mbox{ für phi(n,n) definiert}\\ undef & \mbox{sonst} \end{cases} [/mm]

mu-rekursiv ist (man koennte auf den ersten Blick das Gegenteil vermuten, da ja zur
Definition fon f die universelle Funktion (man sagt auch: Goedel-Numerierung) der
mu-rek. Funktionen verwendet wird.

Intuitiv ist es klar, dass f mu-rekursiv ist, da es sich um eine berechenbare (implementierbare) Berechnungsvorschrift handelt. Formal entsteht f aus der Funktion phi (die vorher als mu-rekursiv nachgewiese wurde), der Addition und der konstanten
Funktion  x |-> 1  durch Einsetzung.

Der Definitionsbereich von f ist nach Definition genau der von n -> phi(n,n),
also die Menge K, die als Halteproblem bekannt ist.

Viele Gruesse,

Mathias



Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de