Chữ số của Giáo hội chuyển thành int không có ngôn ngữ nguyên thủy

Question

Có thể chuyển đổi số nhà thờ thành biểu diễn số nguyên mà không sử dụng ngôn ngữ nguyên thủy như add1 không?

Tất cả các ví dụ tôi đã đi qua sử dụng một nguyên thủy để dechurch để int

Ví dụ:

plus1 = lambda x: x + 1 
church2int = lambda n: n(plus1)(0) 

Ví dụ 2:

(define (church-numeral->int cn) 
    ((cn add1) 0)) 

Tôi đang thử nghiệm với một lisp vi intepretter (chỉ sử dụng 10 quy tắc của John McCarthy) và muốn hiểu liệu điều đó có thể được thực hiện mà không cần thêm nguyên thủy hay không.

Answer 1

No. int, như bạn mô tả, là một loại giá trị nguyên thủy, không phải là hàm. Bạn không thể thao tác như vậy int s ở tất cả mà không có nguyên thủy (không có add1, làm thế nào bạn sẽ nhận được để 1 từ 0?). Tuy nhiên, bạn chắc chắn có thể chuyển đổi giữa hai bảng mã tự nhiên khác nhau của Giáo hội mà không sử dụng nguyên thủy, miễn là ngôn ngữ của bạn là Turing-complete mà không có những nguyên thủy đó.

Answer 2

Loại số nguyên không nằm trong danh sách các thủ tục nguyên thủy sơ cấp Lisp của McCarthy - bạn chỉ có chức năng ở cấp đó, không tồn tại các loại dữ liệu khác. Đó là lý do tại sao các số nguyên cần được biểu diễn như các hàm (ví dụ, sử dụng các số của Giáo hội) nếu chúng ta tuân thủ nghiêm ngặt định nghĩa tối giản như vậy của Lisp. Vì vậy, câu trả lời là không. Bạn không thể chuyển đổi thành loại dữ liệu chưa tồn tại.

Bây giờ giả sử rằng chúng tôi thêm số nguyên làm nguyên tử trong ngôn ngữ (lưu ý rằng việc thêm kiểu dữ liệu mới vào ngôn ngữ vượt quá 7-10 thủ tục nguyên thủy được đề cập). Để đơn giản hơn nữa, giả sử chúng ta chỉ cần thêm một số, số không - sau đó chúng ta vẫn cần hoạt động add1 để tạo phần còn lại của số nguyên, theo yêu cầu Peano axioms, yêu cầu sự tồn tại của hoạt động kế thừa cho tự nhiên số tồn tại. Một lần nữa, chúng tôi không thể chuyển đổi từ số Giáo hội thành số nguyên mà không cần ít nhất có số không là nguyên tử và hàm add1.