chien2311
Enterprise Admin
Tổng số bài gửi : 1224
Sinh nhật : 23/11/1988
 |  Tiêu đề: Hàm đệ qui nguyên thuỷ  Thu Mar 25, 2010 9:03 pm | |
| HÀM ĐỆ QUY:
một cách khái quát, HĐQ là những hàm tính được theo từng bước qua các giá trị tính được ở các bước trước đó. Một cách chính xác, cho các hàm số f(x1,…xn, y), φ (x1,..., xn) vày (x1,..., xn, y, z) với giá trị của các biến số và các hàm số là những số nguyên không âm, ta nói hàm số f(x1,... xn, y) nhận được từ φ (x1,..., xn) và ψ (x1,..., xn, y, z) bằng phép đệ quy nguyên thuỷ nếu f(x1,..., xn, 0) = φ (x1,..., xn) f(x1,..., xn, y + 1) = ψ(x1,..., xn, y, f(x1,...,xn, y)). Ta nói φ (x1,..., xn) nhận được từ f(x1,..., xn, y) bằng phép toán tối tiểu hoá nếu nó được xác định và bằng y khi và chỉ khi f(x1,..., xn, 0),..., f(x1,..., xn, y - 1) xác định và có giá trị khác 0, còn f(x1,...,xn, y) = 0. Hàm số gọi là HĐQ nguyên thuỷ nếu nó có thể nhận được từ các hàm đơn giản nhất (O(x) = 0, S(x) = x + 1, Imn (x1,..., xn) = xm) bằng các phép lấy hàm hợp
và phép đệ quy nguyên thuỷ. Hàm số gọi là HĐQ bộ phận nếu nó nhận được
từ các hàm đơn giản nhất, bằng phép lấy hàm hợp, phép đệ quy nguyên
thuỷ và phép tối tiểu hoá. HĐQ bộ phận gọi là HĐQ hoàn toàn nếu nó xác
định khắp nơi.
Đây là một khái niệm quan trọng trong toán lôgic và tin học lí thuyết.
Định đề Chơt nói rằng: lớp các HĐQ trùng với lớp các hàm "tính được"
(theo một cách xây dựng nào đó). Chẳng hạn, lớp HĐQ bộ phận trùng với
lớp hàm tính được bằng máy Turinh (Turing).Nguồn : © Bản quyền 2005 thuộc Viện Từ điển học và Bách khoa thư Việt Nam - Phát triển bởi: 3CSoft | |
|
