Προβλήματα Μαθηματικών

6 Μαΐου, 2008

Μην περιμένετε σχεδόν τίποτα από τη μηχανή

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Themis Mitsis @ 12:28 πμ

Το πρόβλημα αυτό θα σας βοηθήσει να λύσετε το «Μην τα περιμένετε όλα από τη μηχανή«.

Δείξτε ότι υπάρχει μια συνάρτηση f:\mathbb N\to\mathbb N για την οποία δεν μπορείτε να γράψετε ένα πρόγραμμα στον IBM Blue Gene/L που να την υπολογίζει (ο υπολογιστής αυτός μπορεί να έχει πρόσβαση σε σύστημα αρχείων μεγέθους 900TB και έχει ταχύτητα γύρω στα 500 TFLOP).

Προσέξτε πολύ τη διατύπωση και βεβαιωθείτε ότι το πρόβλημα αυτό ζητάει κάτι ευκολότερο από το «Μην τα περιμένετε όλα από τη μηχανή».

5 Σχόλια »

  1. Ένα άλλο hint για αυτού του είδους τα προβλήματα, αν δεν το έχετε ψιλιαστεί ήδη, είναι να δείξετε ότι αν φιξάρεις ν, κάθε συνάρτηση από το {1,…,ν} στους φυσικούς είναι υπολογίσιμη. Μπορείτε να γράψτε ένα πρόγραμμα για κάθε τέτοια συνάρτηση όπως παραπάνω(είναι πολύ εύκολο); Πού βρίσκεται η διαφορά με το πρόβλημα που τέθηκε αρχικά;

    Μου αρέσει!

    Σχόλιο από ikonst — 6 Μαΐου, 2008 @ 12:56 πμ

  2. Υπόδειξη:

    Ένα πρόγραμμα, σε όποια γλώσσα κι’ αν το γράψετε, είναι μια πεπερασμένη ακολουθία από σύμβολα τα οποία παίρνετε από ένα πεπερασμένο αλφάβητο.
    Τώρα, όλοι οι υπολογιστές (του υπερ-υπολογιστή του προβλήματος συμπεριλαμβανομένου) έχουν πεπερασμένη μνήμη.

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — 6 Μαΐου, 2008 @ 8:16 μμ

  3. Κάθε υπολογίσιμη συνάρτηση μπορεί να αντιστοιχηθεί σε ένα φυσικό αριθμό με μια 1-1 και επί απεικόνιση, γιατί από την παραπάνω υπόδειξη βλέπουμε ότι το πλήθος των προγραμμάτων, άρα και των υπολογίσιμων συναρτήσεων, είναι αριθμήσιμο. Έστω λοιπόν f_0,f_1,\cdots,f_n,\cdots η ακολουθία των υπολογίσιμων συναρτήσεων. Θεωρούμε τη συνάρτηση f: \mathbb N \to \mathbb N που ορίζεται ως
    f(n)=1 αν f_n(n)=0 και
    f(n)=0 αν f_n(n)\neq 0.
    Παρατηρούμε ότι η συνάρτηση f δεν ανήκει στην παραπάνω ακολουθία συνεπώς είναι μία μη υπολογίσιμη συνάρτηση από τους φυσικούς αριθμούς στους φυσικούς αριθμούς (στην ουσία στο \{0,1\}).

    Μου αρέσει!

    Σχόλιο από steliosdes — 7 Μαΐου, 2008 @ 9:47 μμ

  4. Ακριβώς.

    Το πλήθος των προγραμμάτων είναι αριθμήσιμο (άρα και το πλήθος των υπολογισίμων συναρτήσεων) αλλά το πλήθος των συναρτήσεων {\mathbb N \to \mathbb N} είναι υπεραριθμήσιμο, ακόμη κι αν υποθέσουμε ότι οι συναρτήσεις αυτές παίρνουν τιμές 0 ή 1 μόνο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — 7 Μαΐου, 2008 @ 9:53 μμ

  5. Πάντως, ο κακομοίρης ο Blue Gene/L αποκλείεται να μπορέσει να υπολογίσει περισσότερες από 128^{9\cdot 10^{14}} συναρτήσεις. Κι’ αν στα προγράμματά σας γράφετε και σχόλια, ακόμα λιγότερες…

    Μου αρέσει!

    Σχόλιο από Themis Mitsis — 8 Μαΐου, 2008 @ 12:40 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Blog στο WordPress.com.