标签: computability

我最近在阅读关于人工生命的文章,并且发表了声明,"康威的生命游戏展示了足够的复杂性,被归类为通用机器." 我只是粗略地了解通用机器是什么,维基百科只让我接近理解,就像维基百科一样.我想知道是否有人可以对这个非常性感的陈述有所了解？

对我而言,康威的"生命游戏"似乎是一种可爱的分心,带来了一些巨大的影响:我无法在那和计算器之间实现飞跃？这甚至是我应该做的飞跃吗？

什么是图灵机,人们为什么一直提到它？我的IBM PC就是我完成计算所需要的!为什么有人关心这些机器？

我读了Ken Thompson的经典论文"信任信任的思考",其中他提示用户写一个Quine作为他的论点的介绍(强烈推荐阅读).

quine是一个计算机程序,它不接受任何输入并生成自己的源代码的副本作为其唯一的输出.

天真的方法只是想说:

print "[insert this program's source here]"

但很快就会发现这是不可能的.我最后用Python 编写了一个,但仍然无法解释"诀窍".我正在寻找一个很好的解释为什么奎因是可能的.

在JavaScript(有些适用于其他地方),你不知道你的代码在哪个目标实现上运行,是否有一种方法可以检测基础排序算法(of Array.sort)是否稳定,只知道它遵循规范？

我可以在webkit (1) (2)中找到2个测试,但这些测试有多可靠？(这可以通过PCP进行检查吗？)我正在寻找一种在数学上合理的解决方案.

这是一个棘手的问题,因为更高级的排序算法可以根据源数组的长度(如Timsort)更改子算法.我一直很困惑,因为我所运行的每一项测试都表明Google Chrome的稳定性,但我见过的所有文档都说它不稳定(来源会告诉你原因).

(通常情况下,我使用此策略使我的排序稳定;它有一个小但有时显着的性能影响)

• 谷歌Chrome/ium - V8
• Safari - JSC
• 火狐 - *猴子 (2) (3)

你如何争论lambda演算是图灵完整的事实(以最简单的方式)？

我正在尝试围绕 lambda 演算，以及它与语言、编译器和二进制代码的关系。lambda 演算等同于图灵机的实际含义是什么，它实际上在哪里表现出来？

我不明白 lambda 演算如何取代图灵机作为计算的理论模型。图灵机是关于改变状态的顺序指令，lambda 演算是关于对某些东西进行评估的表达式。它更抽象，就像它自己的编程语言，而不是如何实际计算某些东西、使事情发生的模型。或者让我们这样说：lambda 演算就像路线图，而图灵机就像汽车模型。这两个如何被认为是等价的？是否有可能在不实施图灵机的情况下在硬件上运行软件？

例如，lisp 编译器和语言如何与 lambda 演算相关？lambda演算在哪一层实现？就 lambda 演算的定义而言，实现是否纯粹？lambda 演算背后的理论在哪里以及如何将语法转换为正在运行的二进制文件？例如，在 lambda 演算中，数字被编码为应用于其他函数 n 次的特殊函数。然而在语法上，我们使用数字文字。所有这些公理在哪里使用？

AFAIK,可计算的数字是数字,其第i个索引可以由图灵机返回.因此,一个不可计算的数字就像一个数字,如果某个其他程序在某些其他输入上停止,则会确定其小数点,等等.但是,再次,PI是一个实数,不能由TM枚举,因此,不能计算？那么哪个学派是正确的？

对于例如,图灵机的不接受自己的编码语言不能被任何图灵机接受.

是Brainfuck图灵完备如果细胞位,+和-操作简单地拨动了一下？是否有一个简单的证据表明,无论细胞大小如何,类似Brainfuck的语言都是图灵完整的,或者我是否需要考虑一个模拟图灵机的程序？我怎么知道是否没有？

编辑:我找到了一个问题的答案:带有位单元的Brainfuck被称为Boolfuck.普通的Brainfuck可以减少到它,所以Boolfuck是Turing-complete.

我在一本关于可计算性的书中读过这篇文章:

(Kleene定理)当且仅当它可以通过应用三个运算联合,连接,重复有限次数从有限语言获得时,语言是规则的.

我正在与"有限语言"斗争.

考虑这种语言: L = a*

它不是有限的.它是一个{0, a, aa, aaa, ...}显然是无限集(0=空字符串)的集合.

所以这是一种无限的语言,对吗？也就是说,"无限集"意味着"无限语言",对吧？

显然,这a*是一种常规语言.它是一种无限的语言.因此,通过Kleene的定理,它不能成为常规语言.矛盾.

我糊涂了.我想我不知道"有限语言"是什么意思.