Các yêu cầu về thuật toán

Mỗi thuật toán đều có một số (có thể bằng không ) các dữ liệu vào (input). Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được lấy từ các tập hợp giá trị cụ thể nào đó. Chẳng hạn, trong thuật toán Euclid ở trên, các số m và n là các dữ liệu lấy từ tập các số nguyên dương .

Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó là các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào, và là kết quả của sự thực hiện thuật toán .Trong thuật toán Euclid, có một dữ liệu ra đó là ƯSCLN g, khi thuật toán dừng lại (trường hợp r=0) thì giá trị của g là ước chung lớn nhất của m và n.

Ở mỗi bước, các bước thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng. Nói rõ hơn là trong cùng một điều kiện hai bộ xử lý cùng thực hiện một thuật toán phải cho cùng một kết quả như nhau. Nếu biểu diễn thuật toán bằng phương pháp thông thường không có gì đảm bảo được ngươì đọc hiểu đúng ý của người viết thuật toán. Để đảm bảo đòi hỏi này, thuật toán cần được mô tả trong các ngôn ngữ lập trình (ngôn ngữ máy, hợp ngữ hoặc ngôn ngữ bậc cao như Pascal.. ). Trong các ngôn ngữ này các mệnh đề được tạo theo các qui tắc cú pháp nghiêm ngặt và chỉ có một nghĩa duy nhất .

Tất cả các phép toán có mặt trong thuật toán phải đủ đơn giản . Điều đó có nghĩa là, các phép toán phải sao cho, ít nhất về nguyên tắc có thể thực hiện bởi con người chỉ bằng giấy trắng và bút chì trong một khoảng thời gian hữu hạn. Chẳng hạn, trong thuật toán Euclid ta chỉ cần thực hiện các phép chia các số nguyên, các phép gán và các phép so sánh r=0 hay r ≠ 0. Điều quan trọng nữa là thuật toán phải có tính đa năng làm việc được với tất cả các tập hợp dữ liệu có thể của đầu vào.

Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào (tức là được lấy ra từ các tập của dữ liệu vào), thuật toán phải dừng lại sau một số hữu hạn bước thực hiện.Ví dụ, thuật toán Euclid thoả mãn điêù kiện này. Bởi vì giá trị của r luôn nhỏ hơn n (khi thực hiện bước 1), nếu r <>0 thì giá trị của n ở bước i (ký hiệu là n_i) sẽ là gía trị của r_i-1 ở bước i-1, ta phải có bất đẳng thức n>r =n₁>r₁ = n₂ > r₂. Dãy số nguyên dương này giảm dần và cần phải kết thúc ở 0, do đó sau một số hữu hạn bước nào đó giá trị của r phải = 0 và thuật toán phải dừng lại.

Với một vấn đề đặt ra, có thể có một hoặc nhiều thuật toán giải .Một vấn đề có thuật toán giải gọi là vấn đề giải được (bằng thuật toán). Chẳng hạn, tìm nghiệm của hệ phương trình tuyến tính là vấn đề giải được. Một vấn đề không tồn tại thuật toán gọi là vấn đề không giải được (bằng thuật toán). Một trong những thành tựu suất xắc nhất của toán học thế kỷ 20 là đã tìm ra những vấn đề không giải được bằng thuật toán. Chẳng hạn thuật toán chắc thắng cho người thứ hai của cờ ca rô hoặc thuật toán xác định xem một máy Turing có dừng lại sau n bước không, đều là những vấn đề không tồn tại thuật toán giải được.