NUMMSQUARED 2006 - Luận án tiến sĩ về nền tảng hàm cho logic toán học
Luận án tiến sĩ NUMMSQUARED 2006 trình bày nền tảng hàm mới cho logic, toán học và khoa học máy tính. Cung cấp cơ sở lý thuyết vững chắc cho ứng dụng tính toán.
Dalhousie University
Logic, Mathematics and Computer Science
Luan An
Luận án
Năm xuất bản
Số trang
300
Thời gian đọc
45 phút
Lượt xem
1
Lượt tải
0
Phí lưu trữ
50 Point
Mục lục chi tiết
Tóm tắt nội dung
I. Nền Tảng Hàm Toán Học Trong NUMMSQUARED
NUMMSQUARED giới thiệu nền tảng mới cho logic, toán học và khoa học máy tính. Hệ thống dựa trên lý thuyết hàm thay vì lý thuyết tập hợp truyền thống. Cách tiếp cận này giải quyết các vấn đề về tính well-founded và coercion. Khung lý thuyết tập trung vào small function extensions và large function extensions. Các khái niệm về miền xác định, miền giá trị được định nghĩa rõ ràng. Hệ thống tránh các nghịch lý trong set theory cổ điển. Tagged small function extensions cho phép coercion stability. Domain extension families đảm bảo tính nhất quán. Normalized large functions cung cấp cơ chế tính toán. Phương pháp này tạo nền tảng vững chắc hơn lambda calculus không kiểu.
1.1. Khái Niệm Small Function Extensions
Small function extensions là khối xây dựng cơ bản. Mỗi extension có miền xác định và rank xác định. Identity small function extensions đóng vai trò đặc biệt. Domain extension families nhóm các extensions liên quan. Specific result xác định giá trị đầu ra cho từng đầu vào. Cấu trúc này đảm bảo tính well-founded của toàn hệ thống.
1.2. Tagged Small Function Extensions
Tagged extensions thêm metadata vào functions. Tag cho phép phân biệt các hàm toán học tương tự. Coercion của tagged extensions tuân theo định lý stability. Untagged extensions là trường hợp đặc biệt. Tag irrelevance theorem đảm bảo tính nhất quán. Cơ chế này hỗ trợ type safety mạnh mẽ.
1.3. Large Function Extensions
Large function extensions xử lý tính toán phức tạp. Computational large functions thực hiện operations cụ thể. Non-computational extensions biểu diễn logic thuần túy. Normalized large functions có dạng chuẩn xác định. Extension và truth value được định nghĩa chính xác. Reduction mechanism tính toán kết quả cuối cùng.
II. Hàm Một Một Và Ánh Xạ Trong Hệ Thống
Các loại ánh xạ được định nghĩa thông qua function extensions. Hàm một một đảm bảo mỗi đầu vào ánh xạ tới đầu ra duy nhất. Hàm toàn ánh bao phủ toàn bộ miền giá trị. Hàm song ánh kết hợp cả hai tính chất. Domain và codomain được kiểm soát chặt chẽ. Rank của functions đảm bảo không có vòng lặp vô hạn. Identity functions bảo toàn cấu trúc. Coercion cho phép chuyển đổi type an toàn. Substitution theorem hỗ trợ biến đổi biểu thức. Normal forms chuẩn hóa representations. Hệ thống này mạnh hơn set theory von Neumann.
2.1. Miền Xác Định Và Miền Giá Trị
Domain của function được định nghĩa qua domain extensions. Specific result xác định image của mỗi element. Codomain là tập hợp tất cả possible results. Rank đảm bảo well-foundedness của definitions. Domain extension families nhóm related domains. Validity checks ngăn chặn contradictions.
2.2. Tính Chất Injective Và Surjective
Injectivity được verify qua specific results. Mỗi domain element map tới unique result. Surjectivity đảm bảo coverage của codomain. Bijective functions có inverse functions. Identity extensions preserve structure hoàn toàn. Tag mechanisms phân biệt isomorphic functions.
2.3. Composition Và Inverse Functions
Hàm hợp được xây dựng từ function extensions. Composition preserves well-foundedness properties. Hàm ngược tồn tại cho bijective functions. Substitution theorem enables function composition. Normal forms simplify composite expressions. Computational combinations optimize evaluations.
III. Lý Thuyết Tập Hợp Và Cải Tiến NUMMSQUARED
NUMMSQUARED vượt qua hạn chế của set theory truyền thống. Von Neumann và Jones approaches có vấn đề về well-foundedness. Hệ thống mới dựa trên functional foundations. Reflection principles được xử lý cẩn thận. Coercion mechanisms tránh type errors. Lambda calculus không kiểu thiếu structure. Typed systems quá restrictive cho mathematics. NUMMSQUARED cân bằng flexibility và safety. Well-founded relations đảm bảo termination. Booleans và natural numbers được define formally. Primitives tạo building blocks cơ bản. Modules organize definitions systematically. Abstract programs enable meta-reasoning.
3.1. Vấn Đề Với Set Theory Cổ Điển
Russell's paradox xuất hiện trong naive set theory. Von Neumann's approach sử dụng ordinals phức tạp. Jones's modifications vẫn có circularity issues. Reflection principles tạo consistency problems. NUMMSQUARED tránh các paradoxes này hoàn toàn. Functional approach eliminates self-reference issues.
3.2. Lambda Calculus Và Hạn Chế
Untyped lambda calculus cho phép non-terminating computations. Typed lambda calculus quá restrictive. Church-Rosser property không đủ cho foundations. NUMMSQUARED combines benefits của cả hai. Normal forms guarantee termination khi needed. Computational freedom retained cho valid operations.
3.3. Well Foundedness Trong NUMMSQUARED
Rank system prevents infinite descending chains. Mỗi function extension có rank xác định. Well-founded relations structure toàn bộ system. Coercion respects rank ordering strictly. Domain extensions maintain well-foundedness invariants. Reduction processes always terminate properly.
IV. Normalized Large Functions Và Tính Toán
Normalized large functions là core của computational model. Extension của function định nghĩa behavior. Truth values emerge từ function evaluations. Reduction mechanism computes normal forms. Computed results là fully evaluated expressions. Natural numbers có normal form representations. Quoted forms preserve structure without evaluation. Unquoted forms trigger computation immediately. Substitution theorem enables variable replacement. Definition lists organize function definitions. Modules group related definitions together. Global names reference module-level definitions. Local names scope to specific contexts. Tuple accessors extract components safely. Primitives provide built-in operations. Constants represent fixed values. Computational combinations compose operations. Non-computational combinations express pure logic.
4.1. Reduction Và Normal Forms
Reduction transforms expressions tới simplest forms. Computed operation evaluates fully. Normal form là canonical representation. Natural numbers reduce tới standard notation. Quoted forms delay evaluation strategically. Unquoted forms force immediate computation. Process always terminates cho valid expressions.
4.2. Substitution Và Definitions
Substitution theorem enables safe replacement. Variables bind tới values correctly. Definition lists maintain consistency. Modules encapsulate related definitions. Global names provide cross-module references. Local names ensure proper scoping. Tuple accessors type-check before extraction.
4.3. Computational Vs Non Computational
Computational extensions perform actual calculations. Non-computational extensions express logical properties. Combinations mix cả hai types appropriately. Dependent products enable type-level computation. Recursion right-hand-sides define iterative processes. Normal form computation handles all cases. System balances expressiveness với decidability.
V. Coercion Stability Và Type Safety
Coercion mechanism cho phép safe type conversions. Tagged small function extensions support coercion. Coercion stability theorem đảm bảo consistency. Tags distinguish structurally similar functions. Untagged extensions không require coercion. Tag irrelevance theorem proves equivalences. Domain extensions validate coercions. Rank preservation maintains well-foundedness. Identity functions coerce trivially. Specific results preserved qua coercion. Computational large functions coerce appropriately. Non-computational extensions maintain logical properties. Type safety emerges từ coercion rules. System prevents invalid conversions automatically. Stability guarantees predictable behavior. Theorem proving verifies coercion correctness.
5.1. Tagged Extensions Và Coercion
Tags add metadata cho type distinction. Coercion converts giữa compatible types. Stability theorem proves coercion consistency. Tagged functions preserve semantic meaning. Untagged functions không need conversion. Tag irrelevance shows when tags unnecessary. Mechanism balances flexibility với safety.
5.2. Rank Preservation Trong Coercion
Coercion must preserve rank ordering. Well-foundedness maintained qua conversions. Domain extensions validate rank compatibility. Identity coercions preserve ranks exactly. Non-identity coercions check ranks carefully. System prevents rank violations automatically. Guarantees termination properties preserved.
5.3. Type Safety Guarantees
Coercion rules prevent type errors. Invalid conversions rejected at definition. Computational safety ensured throughout. Logical consistency maintained across coercions. Dependent types interact correctly. Recursion respects type constraints. System provides strong safety properties.
VI. Ứng Dụng Cho Logic Và Khoa Học Máy Tính
NUMMSQUARED provides foundations cho formal logic. Booleans defined qua function extensions. Truth values emerge naturally từ system. Computational large functions implement algorithms. Abstract programs enable meta-programming. Modules organize code systematically. Definition lists maintain consistency. Global và local names provide scoping. Primitives offer built-in operations. Natural numbers support arithmetic. Dependent products enable advanced typing. Recursion handles iterative computations. Normal forms standardize representations. Substitution supports symbolic manipulation. Theorem proving verifies properties. System suitable cho verified software. Foundations support formal mathematics. Computer science benefits từ rigorous base. Logic programming fits naturally. Functional programming paradigm enhanced.
6.1. Formal Logic Foundations
Booleans defined precisely qua extensions. Truth emerges từ function evaluations. Logical operators implemented as functions. Quantifiers handled qua dependent products. Proof terms correspond tới programs. Propositions-as-types principle applies naturally. System supports constructive logic fully.
6.2. Programming Language Applications
Abstract programs represent meta-level code. Modules organize definitions hierarchically. Global names enable modular programming. Local names provide lexical scoping. Primitives give efficient built-ins. Recursion supports iterative algorithms. Normal forms optimize evaluation strategies.
6.3. Verified Software Development
Formal foundations enable verification. Theorem proving checks program correctness. Type safety prevents runtime errors. Coercion stability ensures predictability. Well-foundedness guarantees termination. System supports certified programming. Rigorous base enables trustworthy software.
Tải xuống file đầy đủ để xem toàn bộ nội dung
Tải đầy đủ (300 trang)Trích đoạn nội dung luận án
Tải xuống để đọc toàn bộNUMMSQUARED 2006A0 EXPLAINED, INCLUDING A NEW WELL-FOUNDED FUNCTIONAL FOUNDATION FOR LOGIC, MATHEMATICS AND COMPUTER SCIENCE by Samuel Howse Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy at Dalhousie University Halifax, Nova Scotia October 2006 © Copyright by Samuel Howse, 2006 ivi Library and Bibliotheque et Archives Canada Archives Canada Published Heritage Direction du Branch Patrimoine de l'édition 395 Wellington Street 395, rue Wellington Ottawa ON K1A 0N4 Ottawa ON K1A 0N4 Canada Canada Your file Votre référence ISBN: 978-0-494-19613-7 Our file Notre référence ISBN: 978-0-494-19613-7 NOTICE: AVIS: The author has granted a non- L'auteur a accordé une licence non exclusive exclusive license allowing Library permettant a la Bibliotheque et Archives and Archives Canada to reproduce, Canada de reproduire, publier, archiver, publish, archive, preserve, conserve, sauvegarder, conserver, transmettre au public communicate to the public by par télécommunication ou par I'Internet, préter, telecommunication or on the Internet, distribuer et vendre des théses partout dans loan, distribute and sell theses le monde, a des fins commerciales ou autres, worldwide, for commercial or non- sur support microforme, papier, électronique commercial purposes, in microform, et/ou autres formats. paper, electronic and/or any other formats. The author retains copyright L'auteur conserve la propriété du droit d'auteur ownership and moral rights in et des droits moraux qui protége cette these. Neither the thesis Ni la thése ni des extraits substantiels de nor substantial extracts from it celle-ci ne doivent être imprimés ou autrement may be printed or otherwise reproduits sans son autorisation.
reproduced without the author's permission. In compliance with the Canadian Conformément a la loi canadienne Privacy Act some supporting sur la protection de la vie privée, forms may have been removed quelques formulaires secondaires from this thesis. ont été enlevés de cette these. While these forms may be included Bien que ces formulaires in the document page count, aient inclus dans la pagination, their removal does not represent il n'y aura aucun contenu manquant.
any loss of content from the thesis. Canada DALHOUSIEUNIVERSITY To comply with the Canadian Privacy Act the National Library of Canada has requested that the following pages be removed from this copy of the thesis: Preliminary Pages Examiners Signature Page (pii) Dalhousie Library Copyright Agreement (piii) Appendices Copyright Releases (if applicable) For the inspirational Dr. River, and Nummists everywhere. Visit http: //nummist.
iv TABLE OF CONTENTS LISTOFTABILES. << ¬ eee xx ABSTRACT. sce senee aiar are XXỈỈ ACKNOWLEDGMENTS. ¬ eee eee oe ee es» XXỈỈ CHAPTER 2 NUMMSQUARED OVERVIEW AND COMPARISON .1 UNTYPED LAMBDA CALCULUS AND IMPROVEMENTS .2 SET THEORY, VON NEUMANNANDJONES.5 WELL-FOUNDEDNESS AND COEROION.ee eee 9 27 REFLECTION.
Q Q ee ee ee ee 10 2. ee HH ee ene 11 2. cc ee ee eee ee ee ee eens 12 CHAPTER4 WHERETO FIND THEFORMALPART. ee ee ee ees 17 6.
ee ee ee ee ee ee 17 63 BOOLEANS. cc ce ee ee es 17 6. Q Q Q Q Q ee ee ko 18 6. ee ko eee ee 19 6.8 WELL-FOUNDED RELATONS.1 SMALL FUNCTION EXTENSIONS.2 DOMAIN AND SPECIFIC RESULT OF A SMALL FUNC- TION EXTENSION .3 RANK OF A SMALL FUNCTION EXIENSION.4 IDENTITY SMALL FUNCTION EXTENSIONS.
ce ee eee en 29 7.6 DOMAIN, DOMAIN EXTENSION AND SPECIFIC RESULT OF A DOMAIN EXTENSION FAMIIY.7 DOMAIN, RANK AND VALIDITY OF A DOMAIN EXTENSION .8 DOMAIN EXTENSION IRRELEVANCE THEOREM .10 TAGGED SMALL FUNCTION EXTENSIONS.11 UNTAGGED, TAG IRRELEVANCE THEOREM, TAGGED AND TAGGABLE. ee ee et ee ee 4] 7.12 DOMAIN, DOMAIN EXTENSION, SPECIFIC RESULT AND RANK OF A TAGGED SMALL FUNCTION EXTENSION .13 IDENTITY TAGGED SMALL FUNCTION EXTENSIONS .14 COERCION OF A TAGGED SMALL FUNCTION EXTEN- SION, AND COERCION STABILITY THEOREM.15 RESULT OF A TAGGED SMALL FUNCTION EXTENSION .17 SOME TAGGED SMALL FUNCTION EXTENSIONS.18 LARGE FUNCTION EXTENSIONS AND TRUTH.19 SOME COMPUTATIONAL LARGE FUNCTION EXTENSIONS .20 SOME COMPUTATIONAL COMBINATIONS OF LARGE FUNCTION EXTENSIONS.21 SOME NON-COMPUTATIONAL LARGE FUNCTION EXTENSIONS AND COMBINATIONS.2 EXTENSION AND TRUTH OF A NORMALIZED LARGE FUNCTION .3 REDUCTION: COMPUTED OF A NORMALIZED LARGE FUNCTION.4 NORMAL FORM OF ANATURALNUMBER.5 QUOTED OF A NORMALIZED LARGEFUNCTION .6 UNQUOTED OF A NORMALIZED LARGE FUNCTION. eee eee ee ee es 87 8.8 SUBSTITUTION AND SUBSTITUTION THEOREM. ee ee ee ee et ee ene 88 8.12 DEFINITIONS, DEFINITION LISTS, MODULES AND ABSTRACTPROGRAMS.O ee HH HH HH ee ko 102 8.14 NORMAL FORM OFAPRIMITIVE.15 NORMAL FORM OF A NORMALIZED CONSTANT.16 NORMAL FORM OF A GLOBALNAME.18 NORMAL FORM OFALOCALNAME.19 LOCAL TUPLE ACCESSOR CHECK.20 NORMAL FORM OF A COMPUTATIONAL NON- NORMALIZED CONSTANT OR COMPUTATIONAL COMBINATION.
ee ee ee ees 108 8. ee ee es 114 8. 0 cee ee es 114 8.12 DEPENDENT PRODUCT RESULT .15 RECURSION RIGHT-HAND-SIDE. ee ee ee ee 120 8.21 NORMAL FORM OF A NON-COMPUTATIONAL NON- NORMALIZED CONSTANT OR NON-COMPUTATIONAL COMBINATION.
eee ee ee ee ens 121 8.3 UNARY UNIVERSAL QUANTIFICATION .4 SMALL UNIVERSAL QUANTIFICATION.5 EQUAISRIGHT-HAND-SIDE. cece eee eee 127 8.22 NORMAL FORM AND VALIDITY OF ALARGE FUNCTION .23 NORMAL FORM AND VALIDITY OF A DEFINITION, DEFINITION LIST OR ABSTRACT PROGRAM .25 SOME TRUE LARGE FUNCTION EXTENSIONS. ce eee eee eee eee 131 8. ee ee et ee ee 133 8.
ee ee et ee ee 134 8. ee ee ee ee es 136 8. ee ee eee 137 8. ee ee eee 138 8.
ee ee eee ee ee ee 142 8.ỘOOQ HQ HH ee 147 8.15 IF-THEN-ELSE. ee eee ee ee eee eee 150 8. ee ee eee 151 8. ce ee ee ee ee ee 152 8.
eee ee ee et ee 153 8. eee eee eee ee ee ee 154 8.26 SOME INFERENCES FROM TRUE LARGE FUNCTION EXTENSIONS. ce eee ee eee 156 8.27 SOME TRUE NORMALIZED LARGEFUNCTIONS.28 SOME INFERENCES FROM TRUE NORMALIZED LARGE FUNCTIONS. ee ee es 158 8.30 PROPOSITION AND VALIDITY OF A PROOF AND SOUNDNESSTHEOREM.32 PROOF UNQUOTED OF A NORMALIZED LARGEFUNCTION.
162 91 PREFACE TO THEFORMALPART.1 COQ TERMS, CONTEXTS, ENVI- RONMENTS, TYPE-CHECKING, REDUCTION, NORMAL FORMS AND CONVERTIBILITY.4 COQ DEPENDENT PRODUCTS, FUNCTIONS AND APPLICATIONS .6 COQ MODULES, COMMANDS AND GLOBAL DECLARATIONS .7 NAMING OF COQ MODULES AND GLOBALDECLARATONS. 167 913 NUMMSQUARED FORMALLY STYLE .1 MAKE DESIRED TYPES EXPLICIT USING TYPECASI1S.3 MAKE REUSABLE TERMS INTO SEPARATE GLOBAL DECLARATIONS .4 USE UNDERSCORE FOR HIERARCHI- CALNAMING.2 FUNDAMENTALS:OPERATORS:MAIN.O ee ee So 169 9.6 | CONNECTIVE BINARY OPERATORS .12 CONNECTIVE QUATERNARY OPERATORS .15 CONNECTIVE QUINARY OPERATORS. 172 93 EFUNDAMENTAILS:PROPOSITONS:MAIN. THECONSTANT PROPOSITIONAL PREDICATE.4 | BINARY PROPOSITIONAL PREDICATES .5 CONNECTTVE BINARY PROPOSITIONAL PREDICATES .6 | TRINARY PROPOSITIONAL PREDICATES.7 CONNECTIVE TRINARY PROPOSITIONAL PREDICATES.8 | QUATERNARY PROPOSITIONAL PREDICATES .9 CONNECTIVE QUATERNARY PROPOSITIONAL PREDICATES .10 QUINARY PROPOSITIONAL PREDICATES .11 _CONNECTIVE QUINARY PROPOSITIONAL PREDICATES.
176 FUNDAMENTALS: BOOLEANS: MAIN. cece e ee ee eee 176 9.6 CONNECTIVE BINARY BOOLEAN PREDICATES.9 | QUATERNARY BOOLEAN PREDICATES.10 CONNECTIVE QUATERNARY BOOLEAN PREDICATES.12 CONNECTIVE QUINARY BOOLEAN PREDICATES. cece 180 FUNDAMENTALS: NATURALS:MAIN. ABBREVIATIONS FOR SOME NATURAL NUMBERS.6 FUNDAMENTALS: NATURALS: EFFICIENT: MAIN .7 FUNDAMENTAIS:UNITS:MAIN.Q QQ ee kia 187 973 UNITEQUAIS.8 FUNDAMENTAIS:OPTIONALS:MAIN.
Q ee HH So 188 983 OPTIONALRELATEDTO .4 OPTIONAL RELATED TO, CONNECTIVE .9 OPTIONAL SELECT, TOELEMENT.9 FUNDAMENTALS: BOOLEANS: AND OPTIONALS .10 FUNDAMENTALS: CHOICES:MAIN.11 FUNDAMENTALS: PAIRS: MAIN .12 FUNDAMENTALS: LISTS: MAIN. eee eee eee 202 9. LH HQ HH HH na 204 9.Q Q Q Q Q HQ HH HH K 205 9128 2 LISTNON-EMPTY.OQ Q Q eee ee ko 206 9. ee eee ee he 206 9.12 THELIST SINGLETON OPERATOR .13 THE LIST SINGLETON BINARY OPERATOR.
eee ee ee ee 208 9.20 NON-EMPTY LIST RELATED TO, CONNECTIVE.21 NON-EMPTY LIST SINGLETON .23 THE NON-EMPTY LIST HEAD OPERATOR. ee ee eee 212 9.13 FUNDAMENTALS: OPTIONALS:ANDLISTS.15 FUNDAMENTAIS:NATURALS:ANDLISTS.16 FUNDAMENTALS: NATURALS: EFFICGIENT:ANDHISIS.2 EFFICIENT NATURAL NUMBERLISTS .3 EFFICIENT NATURAL NUMBER LIST EQUALS .17 FUNDAMENTALS: PAIRS:ANDHISTS.2 PAIROF HEAD AND REST TO NON-EMPTYLIST .18 FUNDAMENTAILS:LISTS:SELECT.Q Q Q Q HH HQ HH ees 217 9.6 LIST SELECT TO ELEMENTSIMPLE.7 LIST SELECT, TO ELEMENTITERATE.9 LIST SELECT, BY ELEMENT, SIMPLE .10 LIST SELECT, BY ELEMENT, ITERATE .11 LIST SELECT, BY ELEMENT, INTRODUCED .12 LIST SELECT, BY ELEMENT, TERMINATED .13 LIST SELECT, BY ELEMENT, SEPARATED .14 LIST SELECT, BY ELEMENT, TOELEMENT.15 LIST SELECT, BY ELEMENT, TO ELEMENT, SIMPLE .16 LIST SELECT, BY ELEMENT, TO ELEMENT, ITERATE .17 LIST SELECT, BY PREFIX, RECURSIVE .19 LIST SELECT, BY PREFRX SIMPLE.20 LIST SELECT, BY PREFIX, ITERATE .21 LIST SELECT, BY PREFIX, TOELEMENT .22 LIST SELECT, BY PREFIX, TO ELEMENT, SIMPLE .23 LIST SELECT, BY PREFIX, TO ELEMENT, ITERATE. ce ee ee es 228 9.31 LIST INTERSECTION, FIRST, CONNECTIVE .32 LISTINTERSECTION,NON-EMPTY.33 LIST INTERSECTION, NON-EMPTY, CONNECTIVE .34 LISTTO BOOLEAN PREDICATE.19 FUNDAMENTALS: OPTIONALS: AND LISTS SELECT.20 FUNDAMENTALS: LISTFUNCTIONS:MAIN.3 LISTFUNCTION TO BOOLEAN PREDICATE .5 SIMPLE LISTFUNCTION TO BOOLEAN PREDICATE .7 SIMPLE LISTFUNCTION ITERATE, CURRY2.8 SIMPLE LISTFUNCTION ITERATE, CUMULATIVE .21 NUMMSQUARED: SYNTAX: ABSTRACT: MAIN .2 NUMMSQUARED DIGIT CHARACTERS.3 NUMMSQUARED DIGIT CHARACTER EQUALS.4 NUMMSQUARED IDENTIFIER START CHARACTERS .5 NUMMSQUARED IDENTIFIER START CHARAC- TER EQUAIS.6 NUMMSQUARED IDENTIFIER CONTINUE CHARACTERS.7 NUMMSQUARED IDENTIFIER CONTINUE CHARACTEREQUALS.9 NUMMSQUARED COMMENT EQUALS.10 NUMMSQUARED SIMPLE IDENTIFIERS .11 NUMMSQUARED SIMPLE IDENTIFIER EQUALS .13 NUMMSQUARED IDENTIFIER EQUALS .14 NUMMSQUARED SIMPLE IDENTIFIER TO NUMMSQUAREDIDENTIFIER.15 NUMMSQUARED NATURAL NUMBER PRIMITIVES .16 NUMMSQUARED NATURAL NUMBER PRIMI- TIVEEQUALS.17 NUMMSQUARED CHARACTER PRIMITIVES .18 NUMMSQUARED CHARACTER PRIMITIVE EQUALS .19 NUMMSQUARED STRING PRIMITIVES.20 NUMMSQUARED STRING PRIMITIVE EQUALS .23 NUMMSQUARED COMPUTATIONAL NORMAL- LZEDCONSTANIS.24 NUMMSQUARED NON-COMPUTATIONAL NORMALZEDCONSTANIS.25 NUMMSQUARED NORMALIZED CONSTANTS .26 NUMMSQUARED COMPUTATIONAL NON- NORMALIZED CONSTANIS.27 NUMMSQUARED NON-COMPUTATIONAL NON-NORMALIZED CONSTANTS.28 NUMMSQUARED NON-NORMALIZED CONSTANTS .30 NUMMSQUARED LARGE FUNCTIONS.31 NUMMSQUARED LOCAL TUPLE ACCESSOR LISTS .36 NUMMSQUARED ABSTRACT PROGRAMS. 266 CHAPTER 10 CONCLUSION Sn ee e ) 267 BIBLIOGRAPHY.
Y LIST OF TABLES 2.1 VON NEUMANN’S AXIOMATIZATION AND COMBINA- TORY LOGICROUGHIYCOMPARED. LIST OF FIGURES 7.1 SMALL FUNCTION EXTENSIONS ee © © © © © © ee ee 6 8 óc 98 lll ell ABSTRACT NummSquared Explained is the thesis version of the comprehensive formal docu- ment NummSquared 2006a0 Done Formally, which is available at http: //nummist. Set theory is the standard foundation for mathematics, but often does not include rules of reduction for function calls. Therefore, for computer science, the untyped lambda calculus or type theory is usually preferred.
The untyped lambda calculus (and several improvements on it) make functions fundamental, but suffer from non- terminating reductions and have partially non-classical logics. Type theory is a good foundation for logic, mathematics and computer science, except that, by making both types and functions fundamental, it is more complex than either set theory or the un- typed lambda calculus. This document proposes a new foundational formal language called NummSquared that makes only functions fundamental, while simultaneously ensuring that reduction terminates, having a classical logic, and attempting to follow set theory as much as possible. NummSquared builds on earlier works by John von Neumann in 1925 and Roger Bishop Jones in 1998 that have perhaps not received suffi- cient attention in computer science.
A soundness theorem for NummSquared is proved. Usual set theory, the work of Jones, and NummSquared are all well-founded. NummSquared improves upon the works of von Neumann and Jones by having reduc- tion and proof, by supporting computation and reflection, and by having an interpreter called NsGo (work in progress) so the language can be practically used. NummSquared is variable-free.
For enhanced reliability, NsGo is an F#/C# .NET assembly that is mostly automati- cally extracted from a program of the Coq proof assistant. As a possible step toward making formal methods appealing to a wider audience, NummSquared minimizes constraints on the logician, mathematician or programmer. Because of coercion, there are no types, and functions are defined and called without proof, yet reduction terminates. NummSquared supports proofs as desired, but not required.
ACKNOWLEDGMENTS Many thanks to Dr. Malcolm Heywood, my PhD supervisor at Dalhousie Univer- sity, for unbounded good ideas, patience and support throughout the lengthy PhD process. Thanks to Dr. Peter Hitchcock for insights into software engineering and pro- gram correctness.
Thanks to Dr. Anthony Cox for discussions about programming lan- guages, and for suggesting many useful improvements to the thesis. Thanks to Dr. Paul Gilmore for discussions about his Intensional Type Theory, and for suggesting many useful improvements to the thesis.
Thanks to Hugo Herbelin for discussions about Coq and type theory, and for suggesting many useful improvements to the thesis.
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ
Từ khóa và chủ đề nghiên cứu
Câu hỏi thường gặp
Luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" nghiên cứu về vấn đề gì?
Luận án tiến sĩ NUMMSQUARED 2006 trình bày nền tảng hàm mới cho logic, toán học và khoa học máy tính. Cung cấp cơ sở lý thuyết vững chắc cho ứng dụng tính toán.
Luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" được bảo vệ tại trường nào?
Luận án này được bảo vệ tại Dalhousie University. Năm bảo vệ: 2006.
Luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" thuộc chuyên ngành gì?
Luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" thuộc chuyên ngành Logic, Mathematics and Computer Science. Danh mục: Khoa Học Máy Tính.
Luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" có bao nhiêu trang?
Luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" có 300 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.
Cách tải luận án "NUMMSQUARED: Nền tảng hàm cho logic, toán học và khoa học máy tính" về máy như thế nào?
Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.