Ισχύει ή δεν ισχύει

[nikolasmer]

Επειδή δεν το ξέρω καθόλου το θέμα ρωτάω μήπως και κατανοήσω κάτι.

Αν εγώ θέλω να αποδείξω μια μαθηματική πρόταση οτί ισχύει για όλους παράδειγμα τους ακέραιους αριθμούς, μπορώ να φτιάξω επίτηδες εναν αλγόριθμο ο οποίος να τρέχει απ' άπειρο ή μέχρι να βρεί ένα αντιπαράδειγμα το οποίο να καταρίπτει την πρότασή μου;
Αν πρέπει να φτιάξω έναν τέτοιο, τότε ανήκει σε κάποια συγκεκριμένη κατηγορία αλγορίθμων αυτός;

Παράδειγμα: Να γίνει αλγόριθμος ο οποίος να υπολογίζει και να εμφανίζει ένα μήνυμα σχετικά με το αν ισχύει ο ισχυρισμός πως οποιαδήποτε τριάδα αριθμών (α,β,γ) μετά από συνεχόμενες αφαιρέσεις μεταξύ των { α = α - β , γ = α - γ , β = β - γ} , προκύπτει η τριάδα (0,0,0). πχ. για την τριάδα αριθμών (α,β,γ,) = (2,3,4) θα έχουμε:

α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,3,4)
β = Α_Τ(β-γ) = 1    με την τριάδα να γίνεται (1,1,4)
γ = Α_Τ(α-γ) = 3    με την τριάδα να γίνεται (1,1,3)
----------------------------------------------------------------
α = Α_Τ(α-β) = 0    με την τριάδα να γίνεται (0,1,3)
β = Α_Τ(β-γ) = 2    με την τριάδα να γίνεται (0,2,3)
γ = Α_Τ(α-γ) = 3    με την τριάδα να γίνεται (0,2,3)
---------------------------------------------------------------
α = Α_Τ(α-β) = 2    με την τριάδα να γίνεται (2,2,3)
β = Α_Τ(β-γ) = 1    με την τριάδα να γίνεται (2,1,3)
γ = Α_Τ(α-γ) = 1    με την τριάδα να γίνεται (2,1,1)
---------------------------------------------------------------
α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,1,1)
β = Α_Τ(β-γ) = 1    με την τριάδα να γίνεται (1,0,1)
γ = Α_Τ(α-γ) = 0    με την τριάδα να γίνεται (1,0,0)
---------------------------------------------------------------
α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,0,0)
β = Α_Τ(β-γ) = 0    με την τριάδα να γίνεται  (1,0,0)
γ = Α_Τ(α-γ) = 0    με την τριάδα να γίνεται (1,0,1)
---------------------------------------------------------------
α = Α_Τ(α-β) = 1    με την τριάδα να γίνεται (1,0,1)
β = Α_Τ(β-γ) = 0    με την τριάδα να γίνεται (1,1,1)
γ = Α_Τ(α-γ) = 0    με την τριάδα να γίνεται (1,1,0)
---------------------------------------------------------------

και συνεχίζεται, γιατί μάλλον παραπάνω για την τριάδα αυτή έχω κάνει κάποιο λάθος.

Κανονικά έπρεπε να έχει βγεί μέχρι τώρα!!

[gpapargi]

Επειδή δεν το ξέρω καθόλου το θέμα ρωτάω μήπως και κατανοήσω κάτι.

Αν εγώ θέλω να αποδείξω μια μαθηματική πρόταση οτί ισχύει για όλους παράδειγμα τους ακέραιους αριθμούς, μπορώ να φτιάξω επίτηδες εναν αλγόριθμο ο οποίος να τρέχει απ' άπειρο ή μέχρι να βρεί ένα αντιπαράδειγμα το οποίο να καταρίπτει την πρότασή μου;

Όχι. Αν βρεις αντιπαράδειγμα τότε αποδεικνύεις ότι η πρόταση δεν ισχύει. Αν δε βρεις αντιπαράδειγμα, τότε δεν έχεις αποδείξει τίποτα... ούτε ότι ισχύει ούτε ότι δεν ισχύει. Μπορεί να υπάρχει λύση μετά από 1 τρισεκατομύριο επαναλήψεις. Μπορεί να θέλει χιλιάδες χρόνια εκτέλεσης του αλγορίθμου μέχρι να φτάσεις στη λύση. Ποτέ δεν ξέρεις γι αυτό δεν έχεις αποδείξει τίποτα.
Ένας συνηθισμένος τρόπος για να δείχνεις ότι μια πρόταση ισχύει για όλους τους θετικούς ακεραίους είναι η επαγωγή. Η λογική της είναι η εξής: Δείχνεις ότι ισχύει για το 1 και μετά δείχνεις ότι αν ισχύει για κάποιον συγκεκριμένο ακέραιο τότε ισχύει και για τον επόμενό του. Έτσι το έχεις δείξει για όλους.