注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Allen小笔记

有时会忘记努力...

 
 
 

日志

 
 

图灵完备  

2010-03-04 11:12:54|  分类: 计算机科学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                        图灵完备   计算机科学  Turing Complete     
   图灵完备是什么意思呢?
 子曰:在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以计算出结果,被称为图灵完备(turing complete)。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的,它(计算机设备)有能力执行条件跳转(“if” 和 “goto”语句)以及改变内存数据。
 如果某个东西展现出了图灵完备,它就有能力表现出可以模拟原始计算机,而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的(C++ template就是图灵完备的),都能解决内存有限的问题。图灵完备的机器都被定义有无限内存,但是机器指令集却通常定义为只工作在特定的,有限数量的RAM上。
    图灵等价是什么?
 子又曰:两台计算机p和q被称为图灵等价仅当p能模拟出q且q能模拟出p.

   说完了图灵,在来说说,Lambda 算子以及closure(在wikipedia上还蛮长的,我慢慢翻译吧)
 子再曰:在计算机科学以及逻辑数学里面,Lambda 算子又被称为λ-calculus。
1.Informal description
 1.1 Motivation
  在计算机科学和数学里面,函数是一个基础的概念。λ-calculus为可计算的函数提供了一套简单的语义,酱紫的话,就可以定义函数式计算机的属性。(也就是说λ-calculus为计算设备提供了函数的支持,原文是:The λ-calculus provides a simple semantics for computation with functions so that properties of functional computation can be studied.
  看下面的两个例子。特征函数 I(x)=x 只有一个输入,x,而且立即返回x(就是说没有对输入做任何的处理)
然而sqadd(x,y)=x*x+y*y却有两个输入,返回平方的和(x^2+y^2).用这两个简单的例子,能有助于我们观察λ-calculus的主要思想。
  第一个结论是函数并不需要一个明确的名字。函数sqadd(x,y)=x*x+y*y可以写成匿名的形式x,y->x*x+y*y
读作“the pair of x and y are mapped to x*x + y*y”.相似的,I(x)=x也可以改写成匿名的形式x->x.
  第二个结论是函数的参数名称并不重要,就是说:x->x 和y->y是同样的函数.
  第三个结论,也是最后一个结论是,任何需要输入两个(或者更多)输入的函数,举个例子来说就是前面提到的sqadd(x,y),都可以变化等价为只有一个输入,且返回函数的函数。举个例子来说:x,y->x*x+y*y可以改写成x->(y->x*x+y*y),我们把这个过程叫做Curring(科里化).

  以后再更新吧。要写的感觉很多。
  评论这张
 
阅读(2830)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017