标签: computability

在进行我自己的BigInteger实现时,我遇到了扩展的GCD算法,这是寻找模乘法逆的基础.由于众所周知的欧几里德方法执行速度太慢,混合和二进制算法的速度只有5-10倍,因此选择Lehmer对经典算法的修改.但困难在于,当谈到描述Lehmer时,我发现的所有书籍(Knuth,应用密码学手册,互联网等)都有同样的缺点:

1. 解释基于几个技巧:
   • 输入数字总是相同的长度;
   • 抽象CPU有签名寄存器,可以同时保存数字和符号;
   • 抽象CPU具有半无限的寄存器,即它永远不会溢出.
2. 仅提供基本GCD算法,而不关注反向辅助因子.

至于第一个问题,我最初感到惊讶的是无法找到任何实际的实现(不要指向我的GNU MP库 - 它不是学习的源),但最终通过反编译微软的实现获得灵感来自.Net 4.0,显然是基于Jebelean撰写的文章" 用于查找长整数GCD的两位数Lehmer-Euclid算法 "的思想.由此产生的功能很大,看起来很可怕,但效果很好.

但Microsoft的库仅提供基本功能,不计算任何辅助因子.嗯,准确的,一些辅助因子都在速记步计算,并且在第一步的辅助因子简单地是初始的,但在执行手写步骤之后,那么他们就不再匹配.我目前的解决方案是将"真实"辅助因子与"替代"辅助因子并行更新(第一步除外),但它使性能降至零以下:此功能现在仅比二进制文件快25-50%基本模式下的方法.因此,问题在于,虽然输入数字仅在长手步骤中完全更新,但辅助因子也会在每个速记步骤的迭代中更新从而摧毁了莱默方法的几乎任何好处.

为了加快速度,我实现了一个"融合乘法 - 加法"函数,因为"融合乘法 - 乘法 - 减法"确实有助于更新输入数字,但这次影响可以忽略不计.另一个改进是基于这样的事实,即通常只需要一个辅助因子,因此另一个辅助因子根本就不能计算.这应该减少开销(或者更多,因为第二个数字通常明显小于第一个数字),但实际上开销仅减少了预期的 25%到50%.

因此,我的问题归结为:

1. 是否有对Lehmer算法的全面解释,与实际硬件(具有有限大小的无符号字)的实际实现相关联？
2. 与上面相同,但是关于扩展的 GCD计算.

因此,尽管我对基本算法的性能感到满意,但是相反的情况适用于扩展操作模式,这在我的情况下是主要的.

虽然一般情况是不可判定的,但许多人仍然可以解决日常使用中相当不足的问题.

在科恩关于计算机病毒的博士论文中,他展示了病毒扫描如何与停止问题等效,但我们有一个完整的行业围绕着这一挑战.

我也见过微软的终结者项目 - http://research.microsoft.com/Terminator/

这让我想问一下 - 停止问题被高估 - 我们是否需要担心一般情况？

随着时间的推移,类型是否会变得完整 - 依赖类型似乎是一个很好的发展？

或者,从另一个角度来看,我们是否会开始使用非图灵完整语言来获得静态分析的好处？

我正在研究一本关于计算的书(Minksy 1967),并且很难将递归函数与循环定义的函数联系起来.具体来说,他要求找到两个函数之间的关系:

Ackermann函数(python中的所有代码):

def a(n,m):
    if n==0:
        return m+1
    if m==0:
        return a(n-1,1)
    return a(n-1,a(n,m-1))

和一个用n个嵌套循环计算的函数:

def p(n,m):
    for i_1 in range(m):
        for i_2 in range(m):
           ...
             for i_n in range(m):
                  m+=1

写这个(用一个循环)的递归方式是:

def p(n,m):
     if n==0:
         return m+1
     for i in range(m):
         m=p(n-1,m)
     return m

或者完全递归的方式来编写它将是:

def p(n,m):
    return P(n,m,m)
def P(n,k,m):
    if n==0:
        return m+1
    if k==1:
        return P(n-1,m,m)
    m=P(n,k-1,m)
    return P(n-1,m,m) 

这两个函数有关联的简单方法吗？我觉得我在迷雾中爬行 - 任何有关如何处理这些问题的见解都会非常感激.另外,有没有办法在不引入第三个参数的情况下实现完全递归循环函数？谢谢.

假设存在图灵机M1,M2,M3,它们识别的语言分别是L(M1),L(M2)和L(M3).以下语言L = {(M1,M2,M3):L(M1),L(M2)和L(M3)不相等}语言是否可判定？递归可枚举？或者都不是？

令 T = {<M> | M 是一个 TM，只要它接受 w}，它就接受 w ^r。
证明 T 是不可判定的。

我对这个问题有两个答案 -圣地亚哥：

5.9
令 T = { <M> | M 是一个 TM， 只要它接受 w } 就接受 w ^r。

假设 T 是可判定的，让决策者 R 决定 T。通过构造一个 TM S从 A _TM减少如下：

• S：在输入 <M,w> 上
  1. 如下创建 TM Q：
     在输入 x 上：
     1. 如果 x 没有表格 01 或 10 拒绝。
     2. 如果 x 的形式为 01，则接受。
     3. 否则（x 的形式为 10），在 w 上运行 M，如果 M 接受 w，则接受。
  2. 运行 R
  3. 如果 R …

众所周知,XOR加密非常弱.但是,如果我有一个由不同(理想的素数)长度的多个键组成的键,它们组合成一个更长的键是多么微弱.例如,我有一个长度为5,9和11的文本键.如果我只是使用XOR加密应用第一个键,那么它应该很容易打破,因为加密字节将每5个字节重复一次.然而,如果我'叠加'这些键中的3个,我得到一个有效的非重复长度为5*9*11 = 495.这听起来对我非常强烈.如果我使用每一行的几首诗作为关键词,那么我的非重复长度将比大多数文件大.这有多强(提供密钥仍然是秘密!:))

据我所知，可以使图灵机执行在磁带上编码的指令的循环或迭代。这可以通过确定行分隔符并使Turing机器返回直到达到行分隔符的特定计数（即在循环内部）来完成。但是，图灵机还能执行递归程序吗？

有人可以描述这种图灵机的各种细节吗？

我想，如果可以通过图灵机执行递归，那么还可以执行Quicksort吗？

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

在HostileFork回答之后更新:我的意思是在regexp中我认为这是不可能的,解析得更强大吗？

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