我们首先部分发展了稳定一致性的数学概念，该概念旨在反映人类的实际一致性。然后，我们将第一和第二个g \“ ODEL不完整定理的概括为稳定为$ 1,2 $ cosististers的正式系统。我们的论点尤其是从第一原理中重新提供了原始不完整定理，使用图灵机器使用Turing Machine语言（可计算）直接构建我们的“ g \ odel句子”，特别是我们不使用对角线引理，也不使用任何元逻辑，而是在集合理论中自然化的证据。在实践中，如此稳定的正式系统可以旨在代表人类的数学输出，以便上述对G \” Odel的著名脱节的形式化，从而阻碍了智力的计算。

在本文中，我将考虑一系列问题，最后关于我们科学和数学的认知局限性的广度和深度。然后，我将提出一种规避此类限制的可能方法。我首先考虑有关智力生物学功能的问题。这将导致有关人类语言的问题，也许是我们有史以来最重要的认知假体。虽然传统上对人类语言提供的感知能力进行了狂欢，但我将强调这是多么局限性（因此受到限制）。这将导致有关人类数学以我们的语言如此深入的疑问，这也受到了深厚的限制。然后，我将所有这些结合在一起，侧向回答本文的指导问题：我们对我们甚至无法想象的一切都能辨别什么？

我们提出了五个基本的认知科学基本宗旨，我们在相关文献中认真地将其确定为该哲学的主要基本原则。然后，我们开发一个数学框架来讨论符合这些颁布宗旨的认知系统（人造和自然）。特别是我们注意，我们的数学建模并不将内容符号表示形式归因于代理商，并且代理商的大脑，身体和环境的建模方式使它们成为更大整体的不可分割的一部分。目的是为认知创造数学基础，该基础符合颁布主义。我们看到这样做的两个主要好处：（1）它使计算机科学家，AI研究人员，机器人主义者，认知科学家和心理学家更容易获得颁发的思想，并且（2）它为哲学家提供了一种可以使用的数学工具，可以使用它澄清他们的观念并帮助他们的辩论。我们的主要概念是一种感觉运动系统，这是过渡系统研究概念的特殊情况。我们还考虑了相关的概念，例如标记的过渡系统和确定性自动机。我们分析了一个名为“足够的概念”，并表明它是“从颁布主义的角度来看”中“认知数学数学”中基础概念的一个很好的候选者。我们通过证明对最小的完善（在某种意义上与生物体对环境的最佳调整相对应）的独特定理来证明其重要性，并证明充分性与已知的概念相对应，例如足够的历史信息空间。然后，我们开发其他相关概念，例如不足程度，普遍覆盖，等级制度，战略充足。最后，我们将其全部绑架到颁布的宗旨。

知识可定义是合理的真实信念（“JTB”）？我们认为，人们可以积极地或负面地回答，具体取决于一个人的真实信仰是否合理，我们称之为足够的原因。为了促进我们的论点，我们介绍了一个简单的基于理性的信念的命题逻辑，并提出了充分性的概念的公理表征。我们表明，此逻辑足以灵活，以适应各种有用的功能，包括由于原因的量化。我们使用我们的框架对比JTB的两位概念进行对比：一个内部家，另一家族。我们认为Gettier案例基本上挑战了内部概念，但不是外科医生。我们的方法致力于一系列关于知识的非押金主义，但它也让我们陷入困境，即知识是否涉及只有足够的原因，或者留下房间的原因不足。我们赞成后者的立场，这反映了一个更温和和更现实的无押金主义。

我们建立了量子算法设计与电路下限之间的第一一般连接。具体来说，让$ \ mathfrak {c} $是一类多项式大小概念，假设$ \ mathfrak {c} $可以在统一分布下的成员查询，错误$ 1/2 - \ gamma $通过时间$ t $量子算法。我们证明如果$ \ gamma ^ 2 \ cdot t \ ll 2 ^ n / n $，则$ \ mathsf {bqe} \ nsubseteq \ mathfrak {c} $，其中$ \ mathsf {bqe} = \ mathsf {bque} [2 ^ {o（n）}] $是$ \ mathsf {bqp} $的指数时间模拟。在$ \ gamma $和$ t $中，此结果是最佳的，因为它不难学习（经典）时间$ t = 2 ^ n $（没有错误） ，或在Quantum Time $ t = \ mathsf {poly}（n）$以傅立叶采样为单位为1/2美元（2 ^ { - n / 2}）$。换句话说，即使对这些通用学习算法的边际改善也会导致复杂性理论的主要后果。我们的证明在学习理论，伪随机性和计算复杂性的几个作品上构建，并且至关重要地，在非凡的经典学习算法与由Oliveira和Santhanam建立的电路下限之间的联系（CCC 2017）。扩展他们对量子学习算法的方法，结果产生了重大挑战。为此，我们展示了伪随机发电机如何以通用方式意味着学习到较低的连接，构建针对均匀量子计算的第一个条件伪随机发生器，并扩展了Impagliazzo，JaiSwal的本地列表解码算法。 ，Kabanets和Wigderson（Sicomp 2010）通过微妙的分析到量子电路。我们认为，这些贡献是独立的兴趣，可能会发现其他申请。

积极推论的中央概念是，物理系统参数概率的内部状态在外部世界的状态下衡量。这些可以被视为代理人的信仰，以贝叶斯先前或后部表示。在这里，我们开始发展一般理论，这将告诉我们何时适合将国家解释为以这种方式代表信仰。我们专注于系统可以被解释为执行贝叶斯滤波或贝叶斯推断的情况。我们使用类别理论的技术提供对存在这种解释的方法的形式定义。

我们在依赖型理论的建设性设定中研究有限一级可靠性（FSAT）。采用统计性和可解锁性的合成账户，我们根据非逻辑符号的一阶签名提供FSAT的全部分类。一方面，我们的发展侧重于Trakhtenbrot的定理，一旦签名包含至少二进制关系符号，就陈述FSAT是不可行的。我们的证据通过从后对应问题开始的许多减少链进行。另一方面，我们为Monadic一阶逻辑建立了FSAT的可解锁性，即签名仅包含大多数Unary函数和关系符号，以及FSAT对于任意令人令人令人享有的签名的统计性。为了展示Trakthenbrot的定理，我们继续减少链条，从FSAT减少到分离逻辑。我们所有的结果都是在越来越多的综合性不可剥离性证据的框架内机械化。

每个已知的人工深神经网络（DNN）都对应于规范Grothendieck的拓扑中的一个物体。它的学习动态对应于此拓扑中的形态流动。层中的不变结构（例如CNNS或LSTMS）对应于Giraud的堆栈。这种不变性应该是对概括属性的原因，即从约束下的学习数据中推断出来。纤维代表语义前类别（Culioli，Thom），在该类别上定义了人工语言，内部逻辑，直觉主义者，古典或线性（Girard）。网络的语义功能是其能够用这种语言表达理论的能力，以回答输出数据中有关输出的问题。语义信息的数量和空间是通过类比与2015年香农和D.Bennequin的Shannon熵的同源解释来定义的。他们概括了Carnap和Bar-Hillel（1952）发现的措施。令人惊讶的是，上述语义结构通过封闭模型类别的几何纤维对象进行了分类，然后它们产生了DNNS及其语义功能的同位不变。故意类型的理论（Martin-Loef）组织了这些物体和它们之间的纤维。 Grothendieck的导数分析了信息内容和交流。

类比制作是人工智能和人工智能的核心，并在这种多样化任务中的应用程序的创造力作为致辞推理，学习，语言习得和故事讲述。本文从第一个原则介绍了一个摘要的类比比例的摘要代数框架，其形式的“$ a $的数量为$ b $ conal通用代数的常规设定中的$ c $ d $ d。这使我们能够以统一的方式比较可能跨越不同域的数学对象，这对于AI系统至关重要。事实证明，我们对类比比例的概念具有吸引力的数学属性。当我们从第一个原则构建我们的模型，只使用普通代数的基本概念，并且我们的模型问题是在文献中预先推出的类似商品比例的一些基本属性，以说服我们模型的合理性的读者，我们表明它可以自然嵌入通过模型 - 理论类型分为一阶逻辑，并从该角度证明类似的比例与结构保留映射兼容。这为其适用性提供了概念证据。在更广泛的意义上，本文是朝着模拟推理和学习系统理论的第一步，其潜在应用于基本的AI问题，如致料语言推理和计算学习和创造力。

在概念学习，数据库查询的反向工程，生成参考表达式以及知识图中的实体比较之类的应用中，找到以标记数据项形式分开的逻辑公式，该公式分开以标记数据项形式给出的正面和负面示例。在本文中，我们研究了存在本体论的数据的分离公式的存在。对于本体语言和分离语言，我们都专注于一阶逻辑及其以下重要片段：描述逻辑$ \ Mathcal {alci} $，受保护的片段，两变量的片段和受保护的否定片段。为了分离，我们还考虑（工会）连接性查询。我们考虑了几种可分离性，这些可分离性在负面示例的治疗中有所不同，以及他们是否承认使用其他辅助符号来实现分离。我们的主要结果是（所有变体）可分离性，不同语言的分离能力的比较以及确定可分离性的计算复杂性的研究。

对表示形式的研究对于任何形式的交流都是至关重要的，我们有效利用它们的能力至关重要。本文介绍了一种新颖的理论 - 代表性系统理论 - 旨在从三个核心角度从三个核心角度进行抽象地编码各种表示：语法，综合及其属性。通过介绍建筑空间的概念，我们能够在一个统一的范式下编码这些核心组件中的每个核心组件。使用我们的代表性系统理论，有可能在结构上将一个系统中的表示形式转换为另一个系统的表示形式。我们结构转化技术的固有方面是根据表示的属性（例如它们的相对认知有效性或结构复杂性）的代表选择。提供一般结构转化技术的主要理论障碍是缺乏终止算法。代表系统理论允许在没有终止算法的情况下衍生部分变换。由于代表性系统理论提供了一种通用编码代表系统的通用方法，因此消除了进一步的关键障碍：需要设计特定于系统的结构转换算法，这是当不同系统采用不同的形式化方法时所必需的。因此，代表性系统理论是第一个提供统一方法来编码表示形式，通过结构转换支持表示形式的第一个通用框架，并具有广泛的实用应用。

ALChour \“Ardenfors的AGM发布，Makinson继续代表与信仰变革有关的研究中的基石。Katsuno和Mendelzon（K＆M）通过了AGM假设改变信仰基地，并在命题中的特征agm信仰基地修订有限签名的逻辑。我们概括了K＆M在任意Tarskian逻辑中设置的（多个）基本修订版的方法，涵盖了具有经典模型 - 理论语义的所有逻辑，从而涵盖了知识表示和超越的各种逻辑。我们的通用配方适用于“基础”的各种概念（例如信仰集，任意或有限的句子或单句话）。核心结果是表示AGM基本修订运算符和某些“分配”之间双向对应的表示定理：函数映射信仰基础到总数 - 尚未传递 - “偏好”解释之间的关系。与此同时，我们为CAS提供了一个伴侣E当agm andodatience的AGM假设被遗弃时。我们还提供了所有逻辑的表征，我们的结果可以加强生产传递偏好关系的分配（如K＆M的原始工作），根据语法依赖与独立性，引起了这种逻辑的两个表示定理。

形状约束语言（SHACL）是通过验证图表上的某些形状来验证RDF数据的最新W3C推荐语言。先前的工作主要集中在验证问题上，并且仅针对SHACL的简化版本研究了对设计和优化目的至关重要的可满足性和遏制的标准决策问题。此外，SHACL规范不能定义递归定义的约束的语义，这导致文献中提出了几种替代性递归语义。尚未研究这些不同语义与重要决策问题之间的相互作用。在本文中，我们通过向新的一阶语言（称为SCL）的翻译提供了对SHACL的不同特征的全面研究，该语言精确地捕获了SHACL的语义。我们还提出了MSCL，这是SCL的二阶扩展，它使我们能够在单个形式的逻辑框架中定义SHACL的主要递归语义。在这种语言中，我们还提供了对过滤器约束的有效处理，这些滤镜经常在相关文献中被忽略。使用此逻辑，我们为不同的SHACL片段的可满足性和遏制决策问题提供了（联合）可决定性和复杂性结果的详细图。值得注意的是，我们证明这两个问题对于完整的语言都是不可避免的，但是即使面对递归，我们也提供了有趣的功能的可决定性组合。

连续约束满意度问题（CCSP）是一个约束满意度问题（CSP），其间隔域$ u \ subset \ mathbb {r} $。我们进行了一项系统的研究，以对CCSP进行分类，这些CCSP已完成现实的存在理论，即ER完整。为了定义该类别，我们首先考虑ETR问题，该问题也代表了真实的存在理论。在此问题的情况下，我们给出了$ \ compant x_1，\ ldots，x_n \ in \ mathbb {r}的某个句子：\ phi（x_1，\ ldots，x_n）$，其中$ \ phi $ is由符号$ \ {0、1， +，\ cdot，\ geq，>，\ wedge，\ vee，\ neg \} $组成的符号符号的公式正确。 。现在，ER是所有问题的家族，这些家族允许多项式时间降低到ETR。众所周知，np $ \ subseteq $ er $ \ subseteq $ pspace。我们将注意力限制在CCSP上，并具有附加限制（$ x + y = z $）和其他一些轻度的技术状况。以前，已经显示出乘法约束（$ x \ cdot y = z $），平方约束（$ x^2 = y $）或反转约束（$ x \ cdot y = 1 $）足以建立ER-完整性。如下所示，我们以最大的平等约束来扩展这一点。我们表明，CCSP（具有附加限制和其他轻度技术状况）具有任何一个表现良好的弯曲平等约束（$ f（x，y）= 0 $）的CCSP是ER的曲线限制（$ F（x，y）= 0 $）。我们将结果进一步扩展到不平等约束。我们表明，任何行为良好的凸出弯曲且行为良好的凹陷弯曲的不平等约束（$ f（x，y）\ geq 0 $ and $ g（x，x，y）\ geq 0 $）暗示着班级的ER完整性这种CCSP。

我们连接学习算法和算法自动化证明搜索在命题证明系统中：每一种充分强大，表现良好的命题证明系统$ P $，我们证明以下陈述相当，1.可提供学习：$ P $证明p -size电路通过统一分布的子尺寸尺寸电路与成员资格查询进行了学习。 2.可提供自动性：$ P $证明$ P $可通过非均匀电路在表达P尺寸电路下限的命题公式上自动。在这里，如果I.-III，则$ P $足够强大和表现良好。持有：I. $ P $ P-SIMULATES JE \ v {R} \'ABEK的系统$ WF $（通过调节弱鸽子原则加强扩展弗雷格系统$ EF $）; II。 $ P $满足标准证明系统的一些基本属性，P-SIMUTED $ WF $; III。 $ P $可有效地证明一些布尔函数$ H $ H $ H $难以平均为子增长尺寸电路。例如，如果III。保持$ p = wf $，然后项目1和2等同于$ p = wf $。如果在Ne \ Cop Cone $的函数$ H \ IN，这是平均尺寸为2 ^ {n / 4} $的电路，对于每个足够大的$ n $，那么有一个明确的命题证明系统$ p $满意的属性I.-III。，即物品1和2的等价，以$ p $持有。

大多数-AT是确定联合正常形式（CNF）中输入$ N $的最低价公式的问题至少为2 ^ {n-1} $令人满意的作业。在对概率规划和推论复杂性的各种AI社区中，广泛研究了多数饱和问题。虽然大多数饱满为期40多年来，但自然变体的复杂性保持开放：大多数 - $ k $ SAT，其中输入CNF公式仅限于最多$ k $的子句宽度。我们证明，每辆$ k $，大多数 - $ k $ sat是在p的。事实上，对于任何正整数$ k $和ratic $ \ rho \ in（0,1）$ in（0,1）$与有界分比者，我们给出了算法这可以确定给定的$ k $ -cnf是否至少有$ \ rho \ cdot 2 ^ n $令人满意的分配，在确定性线性时间（而先前的最着名的算法在指数时间中运行）。我们的算法对计算复杂性和推理的复杂性具有有趣的积极影响，显着降低了相关问题的已知复杂性，例如E-Maj-$ K $ Sat和Maj-Maj- $ K $ Sat。在我们的方法中，通过提取在$ k $ -cnf的相应设置系统中发现的向日葵，可以通过提取向日葵来解决阈值计数问题的有效方法。我们还表明，大多数 - $ k $ sat的易腐烂性有些脆弱。对于密切相关的gtmajority-sat问题（我们询问给定公式是否超过2 ^ {n-1} $满足分配），这已知是pp-cleanting的，我们表明gtmajority-$ k $ sat在p for $ k \ le 3 $，但为$ k \ geq 4 $完成np-cleante。这些结果是违反直觉的，因为这些问题的“自然”分类将是PP完整性，因为GTMAJority的复杂性存在显着差异 - $ k $ SAT和MOSTION- $ K $ SAT为所有$ k \ ge 4 $。

我们证明，可以通过恒定的深度统一阈值电路模拟输入长度中具有对数精度的变压器神经网络（以及使用输入长度中的线性空间计算的FeedForward子网络）。因此，此类变压器仅在$ \ mathsf {tc}^0 $中识别形式语言，这是由常数深度，多大小阈值电路定义的语言类。这证明了NLP中的实际主张与计算复杂性理论中的理论猜想之间的联系：“注意就是您需要的一切”（Vaswani等，2017），即，只有在所有有效地计算的情况下，变形金刚都能够进行所有有效的计算可以使用日志空间来解决问题，即$ \ mathsf l = \ mathsf p $。我们还构建了一个可以在任何输入上评估任何恒定深度阈值电路的变压器，证明变形金刚可以遵循$ \ Mathsf {tc}^0 $中表示的说明。

我们根据描述逻辑ALC和ALCI介绍并研究了本体论介导的查询的几个近似概念。我们的近似值有两种：我们可以（1）用一种以易访问的本体语言为例，例如ELI或某些TGD，以及（2）用可拖动类的一个替换数据库，例如其treewidth的数据库，由常数界定。我们确定所得近似值的计算复杂性和相对完整性。（几乎）所有这些都将数据复杂性从Conp-Complete降低到Ptime，在某些情况下甚至是固定参数可拖动和线性时间。虽然种类（1）的近似也降低了综合复杂性，但这种近似（2）往往并非如此。在某些情况下，联合复杂性甚至会增加。

Two approaches to AI, neural networks and symbolic systems, have been proven very successful for an array of AI problems. However, neither has been able to achieve the general reasoning ability required for human-like intelligence. It has been argued that this is due to inherent weaknesses in each approach. Luckily, these weaknesses appear to be complementary, with symbolic systems being adept at the kinds of things neural networks have trouble with and vice-versa. The field of neural-symbolic AI attempts to exploit this asymmetry by combining neural networks and symbolic AI into integrated systems. Often this has been done by encoding symbolic knowledge into neural networks. Unfortunately, although many different methods for this have been proposed, there is no common definition of an encoding to compare them. We seek to rectify this problem by introducing a semantic framework for neural-symbolic AI, which is then shown to be general enough to account for a large family of neural-symbolic systems. We provide a number of examples and proofs of the application of the framework to the neural encoding of various forms of knowledge representation and neural network. These, at first sight disparate approaches, are all shown to fall within the framework's formal definition of what we call semantic encoding for neural-symbolic AI.

We first prove that Littlestone classes, those which model theorists call stable, characterize learnability in a new statistical model: a learner in this new setting outputs the same hypothesis, up to measure zero, with probability one, after a uniformly bounded number of revisions. This fills a certain gap in the literature, and sets the stage for an approximation theorem characterizing Littlestone classes in terms of a range of learning models, by analogy to definability of types in model theory. We then give a complete analogue of Shelah's celebrated (and perhaps a priori untranslatable) Unstable Formula Theorem in the learning setting, with algorithmic arguments taking the place of the infinite.