Aufzählbarkeit

SG1

Michael E. schrieb:

Du darfst für dich die berechenbare Funktion f gerne unterteilen in f, g, h, usw. Du musst nur darauf achten, dass das Gesamtkonstrukt berechenbar bleibt.

Und noch eine Frage: Sind die rationalen Zahlen aufzählbar?

Ja, weil sie abzählbar sind.

Das ja ist richtig, die Begrǘndung nicht. Nicht jede abzählbare Menge ist auch aufzählbar!

CStoll

Wurstinator schrieb:

Hallo,
damit eine Menge rekursiv aufzählbar ist, muss es ja eine Funktion f: N->M geben, die surjektiv die Elemente berechnen kann. Darf sie dabei auch beliebig viele Hilfsfunktionen verwenden?

Afaik ist weniger wichtig, daß diese Funktion surjektiv ist - sie muß vor allem berechenbar sein. Und eine Möglichkeit, berechenbare Funktionen zu beschreiben, besteht darin, sie durch µ-Rekursion, primitive Rekursion und Substitution aus einfacheren Funktionen zusammenzubauen.
Also ja, du kannst (und prinzipiell mußt) die verwendete Berechnungsfunktion aus Hilfsfunktionen zusammenbauen, solange diese selber korrekt gebildet wurden und du sie korrekt kombinierst.

Und noch eine Frage: Sind die rationalen Zahlen aufzählbar?

Afair ja - siehe Cantor

Michael E.

SG1 schrieb:

Michael E. schrieb:

Du darfst für dich die berechenbare Funktion f gerne unterteilen in f, g, h, usw. Du musst nur darauf achten, dass das Gesamtkonstrukt berechenbar bleibt.

Und noch eine Frage: Sind die rationalen Zahlen aufzählbar?

Ja, weil sie abzählbar sind.

Das ja ist richtig, die Begrǘndung nicht. Nicht jede abzählbare Menge ist auch aufzählbar!

Da hast du Recht, ich habs aber noch schneller korrigiert Die Bedingungen für rekursiv aufzählbare Sprachen sind natürlich umfangreicher.

Michael E.

CStoll schrieb:

Afaik ist weniger wichtig, daß diese Funktion surjektiv ist - sie muß vor allem berechenbar sein.

Wenn Surjektivität nicht wichtig ist, ist jede Menge rekursiv aufzählbar. Denn als Funktion wähle ich f : N → {ε}.

Wurstinator

Cantor hat doch nur bewiesen, dass die rationalen Zahlen abzählbar sind oder verschweigt Wikipedia mir etwas?

Berechenbarkeit verstehe ich nicht so ganz, da ich noch nicht bei den Turing-Maschinen war und die Berechenbarkeit häufig mit diesen erklärt wird.
Ist eine berechenbare Funktion eine solche, die in jedem Fall (egal, welche Eingabe) nach endlich vielen Schritten beendet wird?

Christoph

Wurstinator schrieb:

Cantor hat doch nur bewiesen, dass die rationalen Zahlen abzählbar sind oder verschweigt Wikipedia mir etwas?

Das ist richtig. Aber die von Cantor beschriebene Funktion ist "offensichtlich" berechenbar (d.h. es ist eine Übungsaufgabe, ein Programm dafür zu schreiben).

Wurstinator schrieb:

Ist eine berechenbare Funktion eine solche, die in jedem Fall (egal, welche Eingabe) nach endlich vielen Schritten beendet wird?

Nein. Eine Funktion f ist berechenbar, wenn es ein Programm gibt, das auf jeder Eingabe x den Wert f(x) ausrechnet.

Zu fragen ob Funktion in einer bestimmten Anzahl Schritte terminiert, ist nicht sinnvoll, weil eine Funktion nur eine Vorschrift ist, welches x auf welches y abgebildet wird. Erst wenn man ein Programm hat, kann man Fragen stellen wie:
Welche Funktion berechnet das Programm?
Terminiert das Programm auf jeder Eingabe?

CStoll

@Michael: OK, da hatte ich das etwas unvollständig in Erinnerung.

@Wurstinator: Es gibt verschiedene Definitionen von Berechenbarkeit, die zueinander äquivalent sind - Turingmaschinen sind nur eine davon. Und es gibt auch Turing-Maschinen, die nicht auf jeder Eingabe anhalten.

Und beim Unterschied Abzählbar vs. Aufzählbar hast du mich wohl auf dem falschen Bein erwischt

Wurstinator

In Ordnung, vielen Dank für die Hilfe

Und beim Unterschied Abzählbar vs. Aufzählbar hast du mich wohl auf dem falschen Bein erwischt

C++ Forumbot

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum Rund um die Programmierung in das Forum Mathematik und Physik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

volkard

Irgendwie habe ich verpaßt, was die offensichtliche Lösung war.
Das folgende C++-Programm zeigt alle positiven rationalen Zahlen an. Daraus was zu machen, das alle anzeigt, ist triv.
Jede kommt nur einmal vor, Kürzen und evtl Verwerfen ist nicht mehr nötig.

#include <iostream>
#include <queue>
using namespace std;

int main(){
    queue<int> band_1;
    queue<int> band_2;

    band_1.push(0);
    band_1.push(1);
    band_1.push(1);
    band_1.push(0);

    for(int i=0;;++i){
        int band_3=band_1.front();band_1.pop();
        int band_4=band_1.front();band_1.pop();
        band_2.push(band_3);
        band_2.push(band_4);
        while(!band_1.empty()){
            int band_5=band_1.front();band_1.pop();
            int band_6=band_1.front();band_1.pop();
            int band_7=band_3+band_5;
            int band_8=band_4+band_6;
            cout<<band_7<<'/'<<band_8<<'\n';
            cin.get();
            band_2.push(band_7);
            band_2.push(band_8);
            band_2.push(band_5);
            band_2.push(band_6);
            band_3=band_5;
            band_4=band_6;
        }
        band_1.swap(band_2);
        cout<<'\n';
    }
}

Dabei gehe ich davon aus, daß es möglich ist, eine Zahlendarstellung zu finden, die es erlaubt, sie auf dem Band hintereinderzuschreiben und zusätzlich sowas wie einen Zahlentrenner, ein BeginOfQueue und EndOfQueue zu haben. Kann man ja machen, indem man pro Ziffer nicht ein Bit, sondern gleich drei schreibt. Sicher wäre ich erst, wenn ich das auf eine Turingmaschine mit z.B. 10 Bändern runtergeschrieben hätte. Mir will scheinen, das könnte klappen.

http://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion