问题标签 [computability]

我为我的网站创建了一个 Sticky 页脚，您可以在此小提琴中查看：http: //jsfiddle.net/Aw6vn/

它适用于 jsfiddle 中的所有浏览器，但是当我将代码放在我的页面中时，它在 IE8-9 中不起作用：

http://s-maof.com/PRO/index2.php?fkapp=2

我也试过：

没有做到这一点。

感谢“我的头疼”，解决方案是编辑掉评论的标题

谢谢！

我已经构建了一个页面，它从数据库动态加载数据并使用 jQuery 向页面添加 html 标签和类

html是

js是

它适用于 FF 和 chrome，但不适用于 IE8。

页面链接是http://www.s-maof.com/PRO/index.php?fkapp=9 （在搜索框中查找“649012” - 只有一个）。

高图表也不起作用（仅在 IE 上）。

谢谢。

如果我有Σ={a}，有什么话Σ*？

Σ*= {a,aa,aaa,aaaa.....}?

谢谢

如果单元格是位，并且 + 和 - 操作只是稍微翻转一下，Brainfuck Turing 是否完整？是否有一个简单的证据证明类似 Brainfuck 的语言无论单元大小如何都是图灵完备的，还是我需要考虑一个模拟图灵机的程序？如果没有，我怎么知道？

编辑：我找到了问题的答案：Brainfuck with bit cells 被称为Boolfuck。普通的 Brainfuck 可以简化为它，所以 Boolfuck 是图灵完备的。

也就是说，图灵机能否将形式系统 S 作为其输入并确定 S 是否是图灵完备的？

我认为这是一个无法确定的问题，对吗？

如果它是不可判定的，为什么我们（作为人类）可以决定图灵完备性？

在 JavaScript（在其他地方有些适用）中，您不知道您的代码在哪个目标实现上运行，有没有一种方法可以检测底层排序算法 (of Array.sort) 是否稳定，只知道它遵循规范?

我可以在 webkit (1) (2)中找到 2 个测试，但是这些测试的可靠性如何？（这个检查可以用PCP完成吗？）我正在寻找一个数学上合理的解决方案。

这是一个棘手的问题，因为更高级的排序算法可以根据源数组的长度（如 Timsort）更改子算法。我一直很困惑，因为我运行的每个测试都显示谷歌浏览器的排序是稳定的，但我看到的所有文档都说它不稳定（来源会告诉你原因）。

（通常，我使用这种策略来使我的排序稳定；它对性能的影响很小但有时很明显）

• 谷歌浏览器/ium - V8
• 野生动物园-JSC
• 火狐 - *猴子 (2) (3)

在进行自己的 BigInteger 实现时，我遇到了扩展 GCD 算法，这是查找模乘逆的基础。由于众所周知的欧几里得方法执行速度太慢，混合和二进制算法仅快 5-10 倍，因此选择了 Lehmer 对经典算法的修改。但困难在于，在描述 Lehmer's 时，我发现的所有书籍（Knuth、Handbook of Applied Cryptography、Internets 等）都有相同的缺点：

1. 解释基于几个技巧：
   • 输入数字始终具有相同的长度；
   • 抽象 CPU 有带符号的寄存器，可以同时保存数字和符号；
   • 抽象 CPU 具有半无限的寄存器，即它永远不会溢出。
2. 只提供了基本的 GCD 算法，没有关注逆辅因子。

至于第一个问题，我最初对找不到任何真实世界的实现感到惊讶（不要将我指向 GNU MP 库——它不是学习的来源），但最终通过反编译微软的实现获得了灵感来自.Net 4.0，这显然是基于论文“<a href="http://www.csie.nuk.edu.tw/~cychen/gcd/A%20double-digit%20Lehmer-Euclid% 20algorithm%20for%20finding%20the%20GCD%20of%20long%20integers.pdf" rel="nofollow">一种用于查找长整数 GCD 的两位数 Lehmer-Euclid 算法，作者 Jebelean。生成的函数很大，看起来很吓人，但效果很好。

但是微软的库只提供基本功能，没有计算辅因子。好吧，准确地说，在速记步骤中计算了一些辅因子，在第一步中，这些辅因子只是初始的，但是在执行了速记步骤之后，它们就不再匹配了。我目前的解决方案是与“替代”辅因子并行更新“真实”辅因子（第一步除外），但这会使性能下降到零以下：该函数现在完成的速度仅比二进制快 25-50%基本模式中的方法。所以，问题在于，虽然输入数字仅在速记步骤中完全更新，但辅因子也在每个速记步骤的迭代中更新，从而几乎破坏了 Lehmer 方法的任何好处。

为了加快速度，我实现了一个“融合乘加”功能，因为“融合乘乘减”确实有助于更新输入数字，但这次影响可以忽略不计。另一项改进是基于这样一个事实，即通常只需要一个辅因子，因此可以根本不计算另一个辅因子。这应该将开销减半（甚至更多，因为第二个数字通常明显小于第一个），但实际上开销仅减少了预期的 25% 到 50% 。

因此，我的问题归结为：

1. 是否有任何关于 Lehmer 算法的全面解释，与实际硬件上的实际实现相关（使用大小有限的无符号字）？
2. 与上面相同，但关于扩展的GCD 计算。

因此，尽管我对基本算法的性能感到满意，但扩展操作模式正好相反，这在我的案例中是主要的。

我在一本关于可计算性的书中读到了这一点：

(Kleene's Theorem) 一种语言是规则的当且仅当它可以通过应用联合、连接、重复有限次数这三个操作从有限语言中获得。

我正在与“有限的语言”作斗争。

考虑这种语言：L = a*

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

所以它是一种无限的语言，对吧？也就是说，“无限集”意味着“无限语言”，对吧？

显然，a*是一种常规语言。它是一种无限的语言。因此，根据 Kleene 定理，它不可能是常规语言。矛盾。

我很困惑。我想我不知道“有限语言”是什么意思。

我在 Computability and Complexity 有一个重复出现，我想知道是否有人有很好的资源来进行这种研究。诸如常规语言、上下文无关和上下文敏感语言之类的东西。

例如：

如您所见，这是一个措辞可怕的问题。我们的讲师给我们的笔记同样糟糕。我真的需要通过这个模块，所以如果有人有很好的资源来研究这些主题，我将不胜感激。

考虑通常称为 TAλ 的简单类型的基本系统。可以证明（由于所谓的主题归约属性和任何可类型化项都是强 β 归一化的事实）

因此，给定一个居住问题 Γ ⊢ X : τ 我们可以有效地构造一个算法，该算法可以非确定性地逐步猜测正态解的形状：(i) X 是 xY_1...Y_n 或 (ii) X 是 λz。是的：

(i) 如果对于某些 n ≥ 0 存在判断 x : σ_1 → ... → σ_n → τ in Γ，则非确定性地选择它，设置 X = xY_1...Y_n 并且（仅当 n > 0 时）考虑并行问题Γ ⊢ Y_1 : σ_1,...,Γ ⊢ Y_n : σ_n

(ii) 如果 τ 是 τ_1 → τ_2，那么对于一个新变量 z，设置 X = λz.Y 并考虑问题 Γ, z : τ_1 ⊢ Y : τ_2。

此外，由于算法每一步约束中的所有类型都是原始输入的适当子类型，因此算法的步数最多是 τ 大小的多项式。因此，上述算法是居住问题的决策过程。

我的问题如下：上述推理有什么问题？我整天都在寻找简单类型的居住问题的决策程序，但是我能找到的所有证明都相当长并且使用复杂的机制（例如长范式、Curry-Howard 同构等）。一定有什么我看不到的。

抱歉，我不习惯 unicode，所以不支持 LaTeX。我还在 MO https://mathoverflow.net/questions/140045/is-there-an-easy-decision-algorithm-for-the-inhabitation-problem-for-simple-type上问了同样的问题，但是 lambda 演算小组在那里似乎不太活跃。