Schrift
Start · Board · Beiträge im Abseits · Sonstige Beiträge (auch Spaß und Sinnloses)
[thread]1917[/thread]

Über Primitive Sinnfreiheit: zieh dich besser warm an



<< |< 1 2 >| >> 17 Einträge, 2 Seiten
renee
 2004-07-14 02:13
#19531 #19531
User since
2003-08-04
14371 Artikel
ModeratorIn
[Homepage] [default_avatar]
danke @kabel... Einige Grundlagen kannte ich dank vieler (z.T. sinnloser Vorlesungen) schon. Dass mit der Ackermann-Funktion hört sich ganz gut an. Ich werde mich wohl in der nächsten Woche mal näher damit beschäftigen...
OTRS-Erweiterungen (http://feature-addons.de/)
Frankfurt Perlmongers (http://frankfurt.pm/)
--

Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
Perl-Entwicklung: http://perl-services.de/
esskar
 2004-07-14 17:09
#19532 #19532
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
hier ist noch ne schnelle lösung mit einer rekursion

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
sub ackermann
{
   my ($n, $m, $seen) = @_;
   
   $seen = {} unless defined $seen;

   while(1)
   {
       if($n == 0)
       {
       	   $seen->{"$n,$m"} = $m+1;       	   
           return ($m+1);
       }
       elsif($m == 0)
       {
           $n--;
           $m = 1;
       }
       else
       {
           my $z = $seen->{"$n,".($m-1)};       	   
           $m = $z || ackermann($n, $m-1, $seen);
           $n--;           
       }
   }
}
betterworld
 2004-07-20 19:44
#19533 #19533
User since
2003-08-21
2613 Artikel
ModeratorIn

user image
[quote=Ishka,20.07.2004, 17:41]unser Informatikprof hat \ immer mit Rückschräge bezeichnet ;)[/quote]
Ishka: Ich habe immer "Rückschläger" verstanden... finde ich auch logischer, da es zu "Backslash" passt...
Lieblingsmodule: CPAN:IPC::System::Simple, CPAN:Path::Class
lichtkind
 2004-07-21 15:45
#19534 #19534
User since
2004-03-22
5681 Artikel
ModeratorIn + EditorIn
[Homepage]
user image
cursiv (auch italic genannt) war die schreibschrift im alten rom
damals schrieb man mit einem stift auf wachstafeln und irgendwie muss das in kursiv leichter oder leichter schnell gegangen sein
Wiki:Tutorien in der Wiki, mein zeug:
kephra, baumhaus, garten, gezwitscher

Es beginnt immer mit einer Entscheidung.
kabel
 2004-07-14 01:43
#19535 #19535
User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]
tja, dumm gelaufen ;) harhar
ich will dich definitiv NICHT vom studium abhalten.

da musst du deine studienordnung befragen, in welche fächer du vordiplomsprüfung machen musst.
dann kannst du dich mal gezielt nach art der vorlesung, schwierigkeit, ... informieren.
tutoren sollen da ganz hilfreich sein, whatever.

und bei der gelegenheit solltest du dich auch mal über die mathematik an deiner uni informieren. ;)
da gehts teilweise auch recht deftig zur sache.

AFAIK wird das zeugs da unten bei uns nicht geprüft.
das ist also mein eigenes interesse, sozusagen. kein grund zur panik ...
-- stefan
kabel
 2004-07-14 01:04
#19536 #19536
User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]
ich hoffe wirklich, hier ist noch jemand der sich damit auskennt und mich ggf. korrigieren kann!
ansonsten meine aussagen auf die goldwaage legen. ihr wisst ja, dass das von einem absolute n00b kommt,
also falls es oberlehrerhaft klingt, ruhig auf mich draufkloppen!

bitte nicht nach der motivation fragen, renee hat gefragt, ob ich nen extra thread dafür aufmach.
nun, hier ist er, und ich benutze das schamlos, um mich auf meine thinf-klausur vorzubereiten.

:)

[html]<hr />[/html]

fang mal an, kabel! ein grober überblick wär z.b. net schlecht...

es geht in die tiefen der theoretischen informatik. da können wir grob die themen
- formale sprache (sprachtypen, grammatiken, ...),
- automatentheorie (automaten, die die verschiedenen sprachtypen erkennen, turingmaschine, regulärer automat, kellerautomat etc),
- komplexitätstheorie (landau, komplexitätsklassen (z.b. P)) und
- berechenbarkeitstheorie (was ist überhaupt berechenbar?)
unterscheiden (unvollständig).

in welchem bereich fällt nu diese komische ackermannfunktion?

wie ich schon andeutete, hat die ackermannfunktion was mit berechenbarkeit zu tun. berechenbarkeit heisst in diesem fall /intuitive/ berechenbarkeit. berechenbar heisst eine funktion f genau dann, wenn man ein /allgemeines verfahren/ angeben kann, dass f berechnet (z.b. ein algorithmus in pseudocode).

warum jetzt auf einmal _intuitive_ berechenbarkeit?
reichts net von einer funktion zu wissen, dass sie berechenbar ist?

ganz so einfach ist das nicht. was heisst denn berechenbar im /intuitiven/ sinne genau? genau, das interpretiert man sich so zusammen. das ist aber nicht erwünscht, die grundbegriffe müssen exakt definiert sein, ansonsten ist die theorie nicht viel wert; nämlich genau gar nichts.

also wird die definition von _intuitiv berechenbar_ auf die definition des _allgemeine verfahrens_ abgeschoben?

ich gehe mal davon aus, dass du weisst, was eine turingmaschine ist.

denk dir an dieser stelle einfach eine turingmaschine. d.h. eine funktion f ist genau dann intuitiv berechenbar, wenn es eine turingmaschine t gibt, die f berechnet. das ist zwar nicht bewiesen, wird aber heute als gültig angenommen (sog. Churchsche These)

zurück zum thema: ist die ackermannfunktion intuitiv berechenbar? oder was hat die sonst damit zu tun?

ja, die ackermannfunktion ist intuitiv berechenbar per se, da ja die berechnungsvorschrift angebbar ist.

um zu erklären, was diese funktion mit der intuitiven berechenbarkeit zu tun hat, muss ich ein wenig ausholen:

D. Hilbert hat 1926 die vermutung aufgestellt, dass jede berechenbare funktion primitiv-rekursiv ist. Widerlegt worden ist er von einem Herrn Ackermann ( klingelingeling! ), der eine totale Funktion angegeben hat, die nicht primitiv-rekursiv ist.

Jaja, der Hilbert hatte es schon nicht leicht. Er versuchte auch, die mathematik zu "retten" (bzw. den satzvorrat der mathematik), indem er die widerspruchsfreiheit der basisaxiome zeigen wollte ("Hilbert-Programm"). dazu sag ich dann nur noch den namen Kurt Gödel ...

du schwafelst zuviel. erstmal eine begriffsbestimmung. was ist denn _primitive rekursion_? und wann ist eine funktion _total_?

ich beginne mit dem begriff "total". machen wir uns dazu erstmal klar, von welchen funktionen wir hier reden. es geht um funktionen, die von N*N*...*N nach N abbilden. zu abstrakt? beispiel: die funktion f: N*N*N->N, f(a, b, c) = a*b*c bildet drei natürliche zahlen auf das produkt dieser ab. eine funktion heisst genau dann total, wenn sie für jede mögliche eingabe ein ergebnis liefert.

gibts denn funktionen, bei denen des net so ist?

funktionen gibt es viele, aber wie ich weiter unten ausführen werde, sind alle hier zu betrachtenden funktionen total.
deswegen nur als klitzekleiner ausblick: suchvorgänge führen zu /partiellen/ funktionen (partiel := nicht total), z.b. ist die berechnungsvorschrift m/n (division) für n=0 undefiniert, für n!=0 ist m/n das kleinste z so dass (z+1)*n>m ist; ganzzahldivision! und nicht mal das, denn wir haben nur natürliche zahlen zur verfügung.

puh, na gut, mach mal weiter ...

primitiv rekursive funktionen sind nun eine klasse von funktionen, die auf eine ganz bestimmte art und weise erzeugt werden. hier ist v.a. folgende tatsache interessant: alle primitiv rekursiven funktionen sind aufgrund ihrer konstruktion total. da hilbert gesagt hat, dass alle effektiv berechenbaren funktionen primitiv-rekursiv sind, sagt er also auch, dass alle effektiv berechenbaren funktionen total sind.

und genau in diese kerbe trifft die ackermannfunktion. sie ist zwar einerseits total, andererseits aber nicht primitiv-rekursiv.

:blitz:, widerspruch

die genaueren zusammenhänge und einen beweis erspare ich mir hier. geht definitiv zu weit.
wieder nur ein hinweis: die ackermannfunktion wächst schneller als alle primitiv rekursiven funktionen.
des hab ich selber auch net gepeilt, vielleicht jetzt, durch das erneute nachdenken?!

ich erinnere mich da noch an die µ-rekursivität, die du mal erwähnt hast ...

ach ja. die ackermannfunktion ist µ-rekursiv. diese funktionsklasse ist ziemlich mächtig. zu den konstruktionsvorschriften der primitiv-rekursiven funktionen kommt ein sog. µ-operator dazu mit folgender semantik: (f(x) = µzPxz)

sprich: f an der stelle x ist das kleinste z, so das Pxz wahr ist, falls ein solches z überhaupt existiert, ansonsten 0. Pxz ist dabei ein zweistelliges Prädikat (=Funktion mit Wertebereich {wahr,falsch}). bei prädikaten ist präfix-notation üblich.

[s]so das sagt jetzt keinem was[/s] (jetzt vielleicht schon), Crian hab ich die falsche definition gepostet (grummel, nämlich die des beschränkten µ-operators), und ansonsten bin ich jetzt erstmal "bedient".

ich auch. gute nacht.

[html]<hr />[/html]

UPDATES:
1. den begriff der effektivität rausgeschmissen. da er in der literatur nicht vorkommt, wird er nur verwirren.
komischerweise passt es jetzt auch mit der chuchschen these ...
2. erklärung zum µ-operator ergänzt.
\n\n

<!--EDIT|kabel|1089789434-->
-- stefan
esskar
 2004-07-14 03:13
#19537 #19537
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
bei uns gehört der ganze kram von kabel zum grundstudium! :)

Meines Wissen sind aber die Begriffe "total rekursiv" und "berechenbar" äquivalent, heißt also

Eine Funktion f ist total rekursiv (berechenbar), wenn es eine Tutingmaschine ( TM ) gibt, die auf die Eingabe x den Funktionswert f(x) berechnet.

Für überall definierte Funktionen heißt eine Funktion turing-berechenbar, wenn sie total rekursiv ist. Für parziell definierte Funktionen wird erlaubt, dass die TM für Eingaben, die nicht im Definitionsberech liegen, in eine unendliche Schleife gerät. Wenn das jedoch ausgeschlossen werden soll, ist wohl ausreichend, den Bildbereich der Funktion um ein neues Element # zu erweitern und alle Eingaben außerhalb des Definitionsbereiches auf # abzubilden.

zur "Churchschen These": die formale Definition der turing-Berechenbarkeit erfaßte Klasse von Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.
Die These beinhaltet die Folgerung, dass es keinen umfassenden Berechenbarkeitsbegriff gibt, der nicht außerhalb unserer Intuition liegt. Die These wird dadurch untermauert, dass alle anderen Versuche, den Begriff "berecehnbar" formal zu erfassen, keine größere Klasse berechnbarer Funktionen ergeben haben. Dass andererseits die turing-berecehnbaren Funktionen "berecehnbar" sind, stößt wohl nicht auf Widerspruch. Die These kann (wei kabel schon erwähnt hat) prinzipiell nicht bewiesen werden. Sie könnte höchstens (was aber nirmand glaubt und hofft) falsifiziert werden, indem nicht turing-berechenbare Funktionen als berechenbar "nachgewiesen" werden.
Heutzutage geht man sogar noch einen Schritt weiter und glaubt, dass TMs sogar die Rechenzeit bis auf polynomielle Faktoren "richtig" erfassen. Ein Problem heißt dadurch genau dann effizient lösbar, wenn es von TMs in polynomieller Zeit gelöst werden kann.\n\n

<!--EDIT|esskar|1089794598-->
esskar
 2004-07-14 13:58
#19538 #19538
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
hier mal meine 3 version der ackermann funktion (in lesbarer form):

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
sub ackermann_def
{
    my ($x, $y) = @_;

    if($x == 0)
    {
        return ($y+1);
    }
    elsif($y == 0)
    {
        return ackermann_def($x-1, 1);
    }
    else
    {
        my $z = ackermann_def($x, $y-1);
        return ackermann_def($x-1, $z);
    }
}

sub ackermann_1rekursion
{
    my ($x, $y) = @_;

    while(1)
    {
        if($x == 0)
        {
            return ($y+1);
        }
        elsif($y == 0)
        {
            $x--;
            $y = 1;
        }
        else
        {
            $y = ackermann_1rekursion($x, $y-1);
            $x--;
        }
    }
}

sub ackermann_0rekursion
{
    my ($x, $y) = @_;

    my @stack = ();
    while((defined $x and $x > 0) || ((scalar @stack) != 0))
    {
        if($x == 0)
        {
        	$x = pop @stack;
        	$y++;
        }
        elsif($y == 0)
        {
        	$y = 1;
        	$x--;
        }
        else
        {
        	$y--;
        	push @stack, ($x-1);
        }
    }

    return ($y + 1);
}


wie man sieht, macht eigentlich nur die zweite rekursion probleme!\n\n

<!--EDIT|esskar|1089805274-->
kabel
 2004-07-19 21:31
#19539 #19539
User since
2003-08-04
704 Artikel
BenutzerIn
[default_avatar]
aus: Lüneburg, "Rekursive Funktionen", 2002, S. 3
Quote
Das Wort "rekursiv" erklärt sich durch das lateinische recursio, was "Rücklauf" heißt und auch "das Wiederhochkommen des zuvor Getrunkenen". Letzteres findet sich in Caelius Aurelianus (1950) auf S. 302: ... et recursio sive recursus poti liquoris, ... An dieser Stelle wird die Diphterie beschrieben, die damals noch - im 5. Jahrhundert nach Christus - zum Tode führte.


das buch hat schlappe 80 seiten, [s]was mich sofort zum kopierer pilgern ließ[/s] ...
würde ich nieee machen ;-)
-- stefan
Crian
 2004-07-20 19:20
#19540 #19540
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
Alles Lüge! *kursiv* bedeutet schräg und re rück, also bedeutet rekursiv rückschräg ;) *duck*
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
<< |< 1 2 >| >> 17 Einträge, 2 Seiten



View all threads created 2004-07-14 02:13.