问题标签 [computability]

什么是图灵机，为什么人们一直提到它？我只需要我的 IBM PC 来进行计算！为什么有人关心这些机器？

我最近在阅读关于人工生命的文章，偶然发现了这样的说法，“康威的生命游戏展示了足够的复杂性，可以被归类为通用机器。” 我对什么是通用机器只有一个粗略的了解，而维基百科只是让我与维基百科一样接近理解。我想知道是否有人可以对这个非常性感的声明有所了解？

对我来说，康威的生命游戏似乎是一种可爱的消遣，具有一些巨大的影响：我无法在它和计算器之间进行跳跃？这甚至是我应该做出的飞跃吗？

Stephen Wolfram在 TED 上就他与 Mathematica 和 Wolfram Alpha 的工作进行了精彩的演讲。除其他外，他指出非常简单的计算可​​以产生极其复杂的行为。（他继续讨论他计算整个物理宇宙的雄心壮志。随便说吧，你得给这个家伙一些疯狂的想法......）

作为一个例子，他展示了几个元胞自动机。

您还知道哪些其他简单计算的示例会产生令人着迷的结果？

来自维基百科：

问题 H 是 NP 难的当且仅当存在一个 NP 完全问题 L 是多项式时间图灵可约化为 H（即 L ≤ TH）。

为什么问题（称为 W）从需要 NP 完全减少？为什么它也不能是 NP 难的？看起来你关心的是 W 是“硬”的，而不是它在 NP 中。

想法？

rebol 解析功能是否有限制？它是否能够解析整个 css2/css 3 规范，还是会遇到理论上不可能形成一些规则？

在 HostileFork 回答后更新：我的意思是在正则表达式中我认为这是不可能的，解析更强大吗？

如果是，这是否意味着可以在与 html5 兼容的 rebol vid 中构建浏览器？

众所周知，XOR 加密非常弱。但是，如果我有一个由多个不同（理想情况下是素数）长度的密钥组成的密钥，这些密钥组合起来形成一个更长的密钥，这有多弱。例如，我有一个长度为 5、9 和 11 的文本密钥。如果我只是使用 XOR 加密应用第一个密钥，那么它应该很容易破解，因为加密字节将每 5 个字节重复一次。但是，如果我“覆盖”这些键中的 3 个，我会得到 5*9*11 = 495 的有效非重复长度。这对我来说听起来很强大。如果我使用一首诗的几节经文，每行作为键，那么我的非重复长度将比大多数文件大得多。这会有多强（假设密钥仍然保密！:)）

我正在阅读一本关于计算的书（Minksy 1967），并且很难将递归函数与根据循环定义的函数联系起来。具体来说，他要求找出两个函数之间的关系：

Ackermann 函数（python 中的所有代码）：

还有一个用 n 个嵌套循环计算的函数：

编写此代码的一种递归方式（带有一个循环）是：

或者一种完全递归的编写方式是：

这两个功能有什么简单的联系方式吗？我觉得我在迷雾中四处爬行——您能给我的任何关于如何解决这类问题的见解将不胜感激。另外，有没有办法在不引入第三个参数的情况下实现完全递归循环函数？谢谢。

我们在程序中进行的数值运算受到语言为给定数据类型（或者硬件支持）指定的字节数的限制。假设我可以使用整数来计算我的薪水（即使“短”也足以满足一年的收入！！！；））但不能对比尔·盖茨的财富做同样的事情。因此，我们会选择 long long 之类的东西。但是，我们不是仍然受制于给我们的比特数吗？

那么，如果我在软件中模拟数值运算呢？说一个抽象的类，可以对具有 1000 位数字的数字进行数值运算......当然它会太慢，但我不太担心复杂性，而是更多地关注可计算性......

也许我可以用它在几个月内将 PI 计算到 1000 位的精度，或者在几年内计算出梅森素数并带回家 10 万美元；）

所以现在我的问题是，1）是否已经有任何这样的库可以做这种事情（在 C/C++ 中）。2）如果我要实施一个，你对我有什么建议吗？（+、-、*、/、%、<<、>> 操作我猜应该足够了）

PS：

1. 我是 C/C++ 程序员。

2. 这个限制从我的学生时代就开始困扰我。

AFAIK，图灵可计算数字是图灵机可以返回第 i 个索引的数字。所以一个不可计算的数字就像一个数字，如果其他程序在其他一些输入上停止等等，它的小数点就被确定了。但话又说回来，PI 是一个实数，它不能被 TM 枚举，因此不能被计算？那么哪个学派是正确的呢？

这是我为一门课程解决的问题，我想知道我的解决方案是否正确。我通常不会发布纯数学问题，除非我认为这是无法计算的，因此是计算机科学问题。

给你：

P(S) = 10%

P(Theta1 | S) = P(Theta2 | S) = 96%

P（非 Theta1 | 非 S）= P（非 Theta2 | 非 S）= 98%

除了概率论的常用公理和定义之外，没有其他信息。

特别是，您不会获得有关事件独立性的信息。

您被要求计算 P(S | Theta1 和 Theta2)。

这可以解决吗？如果不是，请提供不可计算性证明。

有趣，嘿？