Nov, 2011

不可预测性和计算不可约性

PDF
TL;DR本文从细胞自动机领域到任何可计算函数 f 的通用领域探讨了分析计算不可约性的几个概念，并提出了一个稳健的形式化定义；通过定义 “在没有遵循模拟自动机或函数的相同路径的情况下无法计算第 n 步骤” 这一概念，我们证明了如果一个对象的行为是计算不可约的，则其第 n 个状态的计算速度不可能比模拟本身更快。
computational irreducibilitycellular automatacomputable functionsimulationcomputation
发现论文，激发创造
  • 关于智能机器的形式上不可判定特征

    研究人工智能机器展现特定行为的逻辑可能性所需的条件，提出了一种与形式语言理论数学上不同但类似的形式化方法，并描述了判定给定任意机器是否具有某种特性的逻辑可能性所需的条件。与先前研究结果不同，发现计算可行性理论中的 Rice 定理通常无法确定任意机器是否具有给定特性，因此决定任意机器是否具有智能、可控性、道德性等特性并不一定是逻辑上不可能的。

    Feb, 2024

  • Peano: 学习形式化数学推理

    本研究探讨在数学中的程序抽象结构，定案例研究并且说明通过 Peano 定理证明环境和可重用抽象的能力，加上恰当的教学大纲，是保障自动化数学推理的长期文化传播的有效方法。

    Nov, 2022

  • 相对论、不可判定性得出相对的 Church-Turing-Deutsch 论题

    通过构建一个相对的计算模型，我们证明了全局图灵机中局部计算机计算其全局模拟器的仿真属性是不可判定的，这些仿真属性引起了相对模型中的特殊相对论效应，我们利用这些性质构建了一个相对的 Church-Turing-Deutsch 论文。

    Jun, 2022

  • 关于条件概率的可计算性

    研究概率论基础中的条件概率可计算性，并证明了存在无法计算的条件概率分布，从而排除了概率推断的通用算法存在的可能性，但在许多常见建模情况下仍然可以进行概率推断。

    May, 2010

  • 神经自动机的不变量

    本文介绍了一种神经动力学系统的符号计算表示理论，旨在研究不同编码下神经自动机的对称性和不变性质，结果表明只有针对等式模式的阶跃函数在重新编码后是不变的，而平均激活水平是不变的。

    Feb, 2023

  • 网络级联中计算的自发出现

    该研究证明了阈值网络中的复杂布尔函数计算是自发发生的，它们通过逻辑自动机的形式表现为计算级联。研究还发现抑制的最佳分数与计算神经科学中的最优信息处理相关。

    Apr, 2022

  • 使用化学反应网络进行确定性函数计算

    本论文介绍了化学反应网络，探讨了其计算行为和函数计算的相关概念，并提出 CRN 可以解决的问题范畴，发现 semilinear predicates 对于 CRN 只是决策而非计算；进一步探究了 semilinear 函数计算的时间复杂度问题。

    Apr, 2012

  • 解释出现

    出现是各个领域中的一个重要属性，可以突如其来地出现，初看并不能预测其出现。因此被认为是相对于观察者的主观属性。一些具有简单和确定性规则的数学系统却展现出突出的行为。研究这些系统为对主观和客观不需要观察者的理解提供了新思路，使得描述计算不可简化成为理解出现现象的关键。

    Aug, 2023

  • 计算生命：简单交互中形成良好的、自复制程序

    研究原生与人工生命起源及自复制体在计算底层中的产生和动态，证明在缺少明确适应度地形的环境中，自复制体经由随机相互作用和自我修改可在计算底层中产生，并展示随着自复制体的崛起，逐渐出现更加复杂的动态。

    Jun, 2024

  • 通过条件模拟实现常识推理：图灵在人工智能中的遗产

    该论文提出了一种基于概率图灵机的计算形式化的 QUERY 抽象，通过条件模拟捕获概率条件，从而将常识推理转化为观察到的统计模型中不确定的世界的概率推断。

    Dec, 2012