Fragen zu Rekursionstheorie - Mathematische Logik

27.06.2010, 11:02	gothino	Auf diesen Beitrag antworten »
Fragen zu Rekursionstheorie - Mathematische Logik Hi, bereite mich auf eine Prüfung zur mathematischen Logik vor und habe im speziellen Probleme mit der rekursiven aufzählbarkeit. Kann mir jemand sagen ob ich bei folgenden Punkten richtig argumentiere? (Es geht bei den Fragen darum zu bestimmen ob eine Menge rekursiv aufzählbar (r.e.), rekursiv ist oder keines von beiden) 1) Der Definitionsbereich einer total rekursiven Funktion ist .... ...würde sagen: rekursiv; wenn man von der Rekursionstheorie spricht sind die Funtionen ja immer definiert als $\begin{eqnarray} f: \mathbb N \to \mathbb N \end{eqnarray}$ . Die natürlichen Zahlen sind also Definitionsbereich einer totalen Funktion und die Menge ist rekursiv 2) Das Bild einer monoton wachsenden total rekursiven Funktion ist ... ... auf alle Fälle rekursiv aufzählbar (da gibt’s ja soweit ich weiß eine Definition dass Bilder total rekursiver Funktionen rekursiv aufzählbar sind); weiß aber nicht ob das Bild auch rekursiv sein könnte wenn die t.r. Funktion zusätzlich monoton wachsend ist 3) A und B sind rekursiv aufzählbare Mengen. Dann ist $\begin{eqnarray} M = \{ab: a \in A, b \in B\} \end{eqnarray}$ .... .... würde sagen rekursiv aufzählbar. A und B sind Bildbereiche von partiell rekursiven Funktionen. M Kann dann partiell rekursive Funktion $\begin{eqnarray} m: \mathbb N \to \mathbb N \end{eqnarray}$ definieren mit $\begin{eqnarray} m(x,y) = xy \end{eqnarray}$ für $\begin{eqnarray} x \in A \wedge y \in B \end{eqnarray}$ und m(x,y) undefiniert sonst. Damit ist M der Bildbereich einer partiell rekursiven Funktion und daher rekursiv aufzählbar 4) A und B sind rekursive Mengen. Dann ist $\begin{eqnarray} M = \{a+b: a \in A, b \in B\} \end{eqnarray}$ .... .... würde auch wieder sagen rekursiv aufzählbar, aber nicht rekursiv. Ich kann eine total rekursive Funktion definieren $\begin{eqnarray} m: \mathbb N \to \mathbb N \end{eqnarray}$ definieren mit $\begin{eqnarray} m(x,y) = x+y \end{eqnarray}$ für $\begin{eqnarray} x \in A \wedge y \in B \end{eqnarray}$ und m(x,y) = 0 sonst. Da das Bild einer total rekursiven Funktion aber auch nur rekursiv aufzählbar ist hilft mir die Tatsache dass A und B rekursiv ist hier nicht speziell weiter, oder? 5) A ist rekursiv. Dann ist die Menge $\begin{eqnarray} \{n: p_{n} \in A\} \end{eqnarray}$ ..... Würde sagen rekursiv. Die Relation dass $\begin{eqnarray} p_{n} \end{eqnarray}$ eine Primzahl ist ist rekursiv, also auch die relation dass $\begin{eqnarray} p_{n}Primzahl \wedge p_{n} \in A \end{eqnarray}$ 6) Die Menge $\begin{eqnarray} \{n: \exists X :U(2n,2x) ist definiert\} \end{eqnarray}$ ist .... ...keine Ahnung hier (U(m,n) ist hire die universale Funktion), ebenso für 7) Die Menge $\begin{eqnarray} \{n: \exists^{\infty} X :U(2n,2x) ist definiert\} \end{eqnarray}$ ist .... Weiß ich keine Lösung. Wäre super wenn mir hier wer Feedback geben könnte Lg gothino
28.06.2010, 11:43	kiste	Auf diesen Beitrag antworten »
Das ist ein sehr spezielles Gebiet der Mathematik. Vielleicht wäre es hilfreich die Begriffe zu definieren. Ich kenne rekursiv aufzählbar im Sinne der Berechenbarkeitstheorie, dort ist es dasselbe wie semi-entscheidbar, bzw. berechenbar mit einer Turingmaschine. Geht es in die Richtung?
28.06.2010, 13:56	gothino	Auf diesen Beitrag antworten »
ja hier geht es wohl um die "Berechenbarkeitstheorie". Wir haben das Rekursionstheorie genannt, aber man kommt ja dann auf den Satz dass eine Funktion genau dann berechenbar (wir haben hier nur mit Registermaschinen gerechnet) ist wenn sie rekursiv ist. Den Begriff rekursiv aufzählbar haben wir dann nur für Mengen definiert, über verschiedene Äquivalente Definitionen: - A Teilmenge von N^{n} ist rekursiv aufzählbar wenn es rekursive Menge B in N^{n-1} deren Projektion A ist (Eine Menge heißt dabei rekursiv wenn ihre charakteristische Funktion rekursiv ist) - A definitionsbereich einer (partiell) rekursiven Funktion - A leer oder A Bild einer (partiell) rekursiven Funktion usw. lg gothino

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »