Υπολογίσιμη συνάρτηση: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Τυπογραφικό |
|||
Γραμμή 10:
== Ορισμός ==
Υπολογισιμότητα μίας συνάρτησης είναι μία άτυπη έννοια. Ένας τρόπος να το περιγράψουμε είναι να πούμε ότι μία συνάρτηση είναι υπολογίσιμη αν η τιμή της μπορεί να ληφθεί από μία [[Αποτελεσματική μέθοδος|αποτελεσματική διαδικασία]]. Με περισσότερη αυστηρότητα, μία συνάρτηση <math>f:\mathbb N^k\rightarrow\mathbb N</math>
είναι υπολογίσιμη αν και μόνο αν υπάρχει μία αποτελεσματική διαδικασία, τέτοια ώστε δίνοντας κάθε κ-[[πλειάδα (μαθηματικά)|πλειάδα]] <math>\mathbf x</math> των φυσικών αριθμών, θα παράγει την τιμή <math>f(\mathbf x)</math>.<ref>{{Πρότυπο:Cite book|title=A Mathematical Introduction to Logic|date=2002|publisher=Elsevier|isbn=0-12-238452-0|edition=Second|location=USA|page=209|last1=Enderton|first1=Herbert}}</ref> Σε συμφωνία με τον ορισμό αυτό, το υπόλοιπο αυτού του άρθρου υποθέτει ότι οι υπολογίσιμες συναρτήσεις παίρνουν πεπερασμένα πολλούς [[Φυσικός αριθμός|φυσικούς αριθμούς]] ως ορίσματα και παράγουν μια τιμή, η οποία είναι ένας φυσικός αριθμός.
Όπως και παραπάνω σε αυτή την άτυπη περιγραφή, υπάρχουν πολλαπλοί επίσημοι, μαθηματικοί ορισμοί. Η κατηγορία των υπολογίσιμων συναρτήσεων μπορεί να οριστεί με πολλά ισοδύναμα [[Mοντέλο υπολογισμού|μοντέλα υπολογισμού]], συμπεριλαμβανομένων
| |||