丘奇-图灵论点与人类认知能力和极限The Church-Turing Thesis and Human Cognitive Ability and Limit Link 本文以丘奇—图灵论点为背景，论述了人类认知能力及其极限，提出了人类认知的可数无限性，和人的认知能力是受递归规律限制的观点。最后，为计算主义认知观提供了一定的计算神经科学的证据。 引言无论人脑和计算机在硬件层次乃至在软件层次可能...
Continue reading

绪论自动机、可计算性与复杂性 计算复杂性理论 可计算性理论 自动机理论 数学概念和术语集合序列和多元组序列 是某些元素或成员按某种顺序排成的一个列表。 与集合一样，序列也可以是有穷序列或者无穷序列。通常把有穷序列称为 多元组 。k个元素的序列称为 k元组。例如，（7,21,57)为一个3元组。 2元组也称为 有序对。 A的 幂集 为A的所有子集的集合。设A为集合{0,1}，则A的幂集为集合...
Continue reading

正则语言计算模型（Computational Model) 有穷自动机有穷状态机(Finite State Machine) 是描述能力和资源极其有限的计算机的模型。 有穷自动机和与之对应的 马尔科夫链（Markov Chains) 常用于识别数据中的模式。 状态图(State Diagram) 从一个状态指向另一个状态的箭头称为 转移 。 有穷自动机的形式化定义有穷自动机是一个5元组$(Q,Σ...
Continue reading

丘奇-图灵论题有穷自动机能较好地描述计算资源较少的设备，下推自动机虽然能描述具有无限存储的设备，但“后进先出”的栈机制使其能力受到限制，还证明了这些模型对于有些非常简单的任务都不能完成，由于它们过于局限，因此不能作为计箅机的通用模型。 图灵机图灵机(Turing Machine)与有穷自动机相似，但它有无限大容童的存储且任意访问内部数据。图灵机是一种精确的通用计算机模型，能模拟实际计算机的所有计算...
Continue reading

可判定性可判定语言与正则语言相关的可判定性问题与上下文无关语言相关的可判定性问题每个上下文无关语言都是可判定的。 停机问题检査一个图灵机是否接受一个给定的串问题是不可解的。 对角化方法康托对测量无限集合的规模问题提出了一个非常好的解决办法。他注意到：对于两个有限集合，如果其中一个集合的元素能与另一集合的元素配对，则它们有相同的规模。这个方法没有凭借计数就比较了规模，因而可以将此思想推广到无限集合...
Continue reading

可计算性理论的高级专题递归定理自引用存在可计算函数$q:Σ^ → Σ^ $，对任意串$w,q(w)$是图灵机$P_w$的描述，$P_w$打印出$w$，然后停机。 递归定理 设$T$是计算函数$t:Σ^ ×Σ^ →Σ^ $的一个图灵机。则存在计算函数$r:Σ^ →Σ^* $的一个图灵机$R$，使得对每一个$w$ 有：$t(w)=t(,w)$ 初看之下，此定理的叙述技术性很强，但实际上，它代表的事情很...
Continue reading

可归约性可用来证明问题是计算上不可解的一种基本方法， 可归约性 。 归约 旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题。 语言理论中的不可判定问题$HALT_{tm}$ (停机问题) 不可判定 线性界限自动机（linear bounded automaton，LBA) 是只有有限存储的图灵机。 映射可归约性将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使...
Continue reading

空间复杂性令$M$是一个在所有输入上都停机的确定型图灵机。$M$的空间复杂度(space complexity) 足一个函数$f:N→N$，其中$f(n)$是$M$在任何长为$n$的输入上扫描带方格的最大数。若$M$的空间复杂度为$f(n)$，则称$M$在空间$f(n)$内运行。 萨维奇定理该定理表明确定型机器可以用非常少的空间模拟非确定型机器。对于时间复杂性，这种模拟似乎需要指数倍地增加时间。对...
Continue reading

时间复杂性度量复杂性在 最坏情况分析（worst-case analysis) 中，即这里考察的形式，考虑在某特定长度的所有输人上的最长运行时间。在 平均情况分析(average-case analysis) 中，考虑在某特定长度的所有输入上的运行时间的平均值。 令$M$是一个在所有输入上都停机的确定型图灵机。$M$的运行时间或者 时间复杂度，是一个函数$f:N→N$,其中$N$是非负整数集合，$...
Continue reading

上下文无关文法上下文无关文法（context-free grammar) ，它能够描述某些应用广泛的具有递归结构特征的语言。 语法分析器（parser) ,它在生成编译代码或解释程序执行前，提取出程序的语义。 与上下文无关文法相关的语言集合称为 上下文无关语言（context-free language) 。 上下文无关文法概述上下文无关文法的形式化定义上下文无关文法 是一个4元组$(V,Σ,R,...
Continue reading