我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 谕示机 >

计算思维的实例——二进制加法的图灵机实现

归档日期:07-05       文本归类:谕示机      文章编辑:爱尚语录

  本文将通过二进制加法的图灵机实现,探索计算思维的内涵,并且对图灵机的功能进行一些讨论。

  注:本文中的语法q0,1,2,R,q1的含义是:q0状态下,读入1,则改写为2,右移,进入q1状态。

  为方便移植,本文中全部采用通俗易懂的伪代码,可转化成Lego版图灵机语言。

  ① q0读入状态,读入“+”则右移跳步,读入“1”则抹为C(记录位置),进入搬运状态q1

  思路:首先我考虑一般位数的加法。基本思路是以“+”号为分隔,将前面的数加到后面去,逐位相加,最后将结果搬运到“=”右侧。

  找到“+”之前(或K之前,即第一个未处理的数字)的第一个数字,进入搬运状态,移动到“=”前(或K之前,即第一个未处理的数字)的一个数字。处理时,先把对应位改写为K(标记已经进行了加法),对加数为1和为0分别考虑。

  进入加法状态。若被加数为0,直接加0或1。注意用a和b分别代替0和1,用来标记加法进度。若被加数为1,加数为0,也是很平凡的情况。若被加数为1,加数也为1,则标记为a(代表0),并左移进入进位状态。

  进位状态:不断左移,如果遇到0则加为1,进入回退状态;若遇到1,则改写为0,继续进位。注意,由于这些被进位的数字还没有被对应的加数处理,所以我们先保留0和1,以免干扰我们对加法进度的判断。

  回退状态:一直左移,直到遇到第一个非K字符,判断是0还是1,进行下一次搬运。

  判断加法结束:当回退时遇到了B,说明此过程中加数的数位全部加完,开始搬运结果至等号右边。

  搬运状态:右移至第一个非K字符,开始搬运。分0和a,1和b两个状态。然后右移至等号。

  由左至右搬运结果。走到第一个非K字符,当a和0转换到q30(搬运写为0),当b和1转换到q31(搬运写为1)

  极端数据:诸如1+1101011111=之类的加数位数和被加数位数相差悬殊的极端情形,并测试长+短和短+长。

  进位测试:11111+1111=和10011+10011=等进行多进位处理。

  互补测试10101+1010=,测试是否会出现因关注进位处理而导致对正常加法的影响。

  回退状态:本来写了两个回退状态,分别用于加法过程中的回退和搬运过程中的回退,考虑优化。

  画完图发现这两个状态可以合并共用,于是可减少10多行代码和2个状态。但是,这同样会造成搬运回退时浪费很多步数移动到第一个字符之前(B,-1位)并从第一个字符返回。

  通过分析和实践发现,即使每次都要进位,最多覆盖一个K,而每次重新进行加法都会增加一个K,故始终可保证结果与未处理的位至少有2个K的间隔。

  Debug时的一个很好的方法是单步调试,通过逐步运行,发现未考虑和考虑不周的状态。

  ① q0读入状态,读入“+”则右移跳步,读入“1”则抹为C(记录位置),进入搬运状态q1

  左移:当遇到1,进入q10(下一次加1);当遇到0,进入q00(下一次加0);当遇到B,则进入q3开始搬运。

  (增加此状态的原因是:防止下列情况的出现:100KKK+100*ab=,当走到a加完回退时,若只用q0,则会一遇到0*就会回退,所以必须保证过K后)

  是0,则右移至第一个未被加的数位,直到遇到a, b或=,进入q01加0状态

  由左至右搬运结果。走到第一个非K字符,当a和0转换到q30(搬运写为0),当b和1转换到q31(搬运写为1)

  是1,则右移至第一个未被加的数位,直到遇到a, b或=,进入q11加1状态

  注:实验2相比于实验3,就是在结果中要补一个前导0的问题。这个问题解决方式很简单,即我们只要给被加数加一个前导0即可,届时如果没有进位覆盖,则0会被搬运过去;如果进位覆盖,则1会被搬运过去。加的方式也很简单:即当读写头第一次移动到“+”号时,将其改写为0即可(人为增加一位)。

  通过图灵机模型,可以通过控制状态转移来实现诸如二进制加法等一些基本的计算任务,在一定程度上验证了图灵机的计算能力。

  评判一个程序/算法优秀的标准是行数还是复杂度?在我的第三个实验的过程中,曾用步数和状态数换行数,但回想起来并不值得。

  对计算思维有了更深的理解:把问题抽象化,构造一种机械性、通用性的算法来解决问题。比特精准、自动执行。对于每一个实验精确的输入和输出,以及每一个规则的操作都是确定的,每一个状态转移都是确定的。

  对正确性的理解:由于图灵机停机问题的不可解性,我认为对正确性的判断只能通过验证的方式,即尽可能多地举出样例去验证结果是否正确。这种方法在实验二中可以实现,但对于实验三这种没有限制的实验可能只能通过跑测试点的方式来验证是否正确。

  对通用性的理解:通过本次实验以及个人理解,我认为读写头如果失去了写的能力,则纸带上字符数恒定,无法完成诸如本实验的加法问题。而如果读写头只能右移,计算能力也会下降,因为记忆能力很有限。限定纸袋长度,也会造成存储空间不足而制约计算能力。而限定状态数,显然如果强制要求实验三用个状态,肯定无法完成。以上内容属个人理解,目前本人没有给出证明的能力。

  下面给出一个关于图灵机计算能力等价性的一些证明:(通过等价DFA来证明计算能力)

  图灵机是一种有限状态机,先来看看图灵机长啥样:再来看看图灵机是如何计算4+3=7的:可以推演一下。不多说。......博文来自:stpeace的专栏

  最近刚考完可计算理论,考前看习题总有一些题让设计一个图灵机来实现某个算法什么的(≖-≖)(虽然考试题里完全没有考到!然而我还是勤勤恳恳地想了很久)当时看图灵机定义看了无数遍,但依然不是很明白怎么设计啊...博文来自:机密母星联络处

  一、题目分析:1.题目:对于任意给定的一台Turing机和任意给定的字符串w(w不含空格),编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果。2.分析:第一步:十进制数转化为二...博文来自:zhang12369的博客

  1原理1.1正数十进制下:5+7=125:01017:0111二进制下两数求和,分三步:各位值相加,不算进位值,二进制亦或运算 计算进位值,二进制与运算,然后左移一位; 对1,2步的结果,重复以上两步...博文来自:ustbbsy的博客

  上一节用单带图灵机模拟了PAL,其实可以用一种称为多带的图灵机来模拟,就像第一篇文章中介绍的那样,多带图灵机是具有多个读写头的图灵机。一个k带图灵机k带图灵机可以定义为一个四元组M=(K,Σ,δ,s)...博文来自:YaphetsBin的专栏

  第一步:将两个二进制数位补齐,在短的前面添0第二步:从后往前做加法第三步:将结果中的字符串反转 注意:此时需要用到StringBuilder,用到append()方法。StringBuffer类中的方...博文来自:pjjp_0309的博客

  个人博客:给定两个二进制字符串,返回它们的和(也是二进制字符串)输入字符串都是非空的,并且只包含0和1字符Example1:Input:a=...博文来自:qiubingcsdn的博客

  图灵机模型与计算机(一)一、图灵机的构成1、一条无限长的纸带(tape)。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字幕的符号,字母表中有一个特殊的符号,就是一个空格,它表示空白。纸带...博文来自:不忘初心,方得始终。

  位运算符:  amp;:位逻辑与  将操作数转换成二进制数,然后将两个二进制操作数对象从低位到高位对齐,每位求与。若操作数对象同一位都为1,则结果对应位为1,若操作数对象同一位为0。   ...博文来自:gaoyubo_taili的博客

  问题描述对于任意给定的一台Turing机和任意给定的字符串w(w不含空格),编程模拟此Turing机的运行过程,要求输出从开始运行起的每一步骤的结果。(本文模拟的是UN+1和UN*2的图灵机)问题分析...博文来自:心温如一

  1、二进制加法基本指令(1)ADD指令格式:ADDDST,SRC该指令把源操作数(SRC)指向的数据与目的操作数(DST)相加后,将结果放到目的操作数(DST)中,所执行的操作:(DST)ß(SRC)...博文来自:abc1498880402的博客

  /*本题的需求是:给出两个字符串,内容是二进制数字,编写计算两个二进制数字和的程序。难点是考虑周到,尤其是最后的一个进位,容易遗忘。*/importjava.util.ArrayList;classA...博文来自:Jack的专栏

  前言虽然我们在编程语言中可以直接使用+-/,但是对某些要求不能用/的情况下,我们有必要了解...博文来自:keke_Xin的专栏

  读计算机原理这本书的的时候涉及到二进制数的加法,个人做个直观的纪律,防止遗忘。计算时,先把两个二进制数对齐(如果十进制一样)1+1为10,此时向上一位进1,0写在本位(如同十进制)不全为1的两个数,直...博文来自:进无止进

  最近在学VHDL和verilogHDL。老师讲到了加法器,我就用Java写了两个程序,一个是普通的逐位加法器,另一个是超前进位加法器。当然,使用VHDL语言编写是最简单的做法。1.逐位加法器packa...博文来自:jiashu233的博客

  二进制总结:int是将其它进制的数转化为十进制,输入两个参数,第一个是输入的值,第二的是进制bin函数是将整数转化为二进制,只有一个参数1int()函数int()函数用于将一个字符串或数字转换为整型。...博文来自:的博客

  计算机为什么使用二进制这是因为二进制在计算机中的表示与计算比十进制和其他进制要简单的多,因为状态少,只有0和1。计算机计算思维与人类的计算思维不一样,人计算较复杂的事务是通过公式或者算法等来计算,而计...博文来自:OneGoal的博客

  图灵机,又称图灵计算、图灵计算机,是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。所谓的图灵...博文来自:Zhangs Wikipedia

  image.pngq111Rq1,其中前两个表示条件,后三个表示动作。(注意:先写入,然后再移动,不要搞反了)。H表示不动。多次不动将会到达停机状态。i1:q111Rq1i2:q1b1Rq2i3:q2...博文来自:weixin_34291004的博客

  数据在计算机内存中是以二进制存储的。几种常用的位运算:与运算&:对应位均为1时为1,其它为0。或运算:对应位均为0时为0,其它为1。异或运算^:对应位不相同时为1,相同时为0.按位取反~:每一位取反...博文来自:一个程序渣渣的小后院

  二进制减法类似于十进制的减法,我们从十进制的减法来推出二进制减法如何进行运算。十进制减法例如74323-47562=26761的运算。灰色部分为计算过程,绿色字为被减一得到的数,红色字为借一后得到的数...博文来自:纪阿爱寺

  引子    某天研究fail-fast机制的时候,去看了看hashCode的实现方式,然后发现每个对象的实现都不一样;于是研究一个String的;于是看到公式:s[0]*31^(n-1)+s[1]...博文来自:ylineyline的专栏

  1.题目描述如何使用位操作分别实现整数的加减乘除四种运算?2.解决方案需要熟练掌握一些常见功能的位操作实现,具体为:常用的等式:-n=~(n-1)=~n+1获取整数n的二进制中最后一个1:n&(-n)...博文来自:NicolasYan的专栏

  年前看了一本科普书籍–《人工智能简史》,作者尼克,早年任职哈佛和惠普,后投资创业。这本书描述了两大人工智能的发展方向,一派主张拟生物大脑(譬如人工神经网络),另一派则主张用逻辑和符号系统(譬如自动定理...博文来自:Camus

  阅读此博客之前需要您对图灵机模型有一定的了解~比如我就是在程序设计方法学中学到的00代码中有很全的注释,如果不想看内容建议直接看二、算法分析(4)整体过程+代码即可~一、题目要求对于任意给定的一台Tu...博文来自:d52370的博客

  原文链接最关键的是下面这段线,大家可以看到我拿两种不同颜色标注了它们最开头的两个数,我们把红色的(左起第一位)符号位进位值和蓝色(左起第二位)相加的进位值进...博文来自:青春不言败

  本学期老师给我们上了一门研究生要上的课程:计算理论导引。起初还不是很理解的,后来觉得从0到1的创造出一个具有思维的及其,这的确是无比的伟大。Turing机:构造分为三部分:1。一条带,一个读写头和一个...博文来自:joyosue

  1、二进制数相加问题2、两个链表的数相加(leetcode第2题)博文来自:zylmjy520的博客

  以二进制的方式输入两个正整数(即0和1组成的字符串),然后输入到一个4则运算(+,-,*,/),按short型计算这两个数的运算结果,并将结果按二进制输出(高位零可不输出)思路:若直接算二进制之间的运...博文来自:巴啦啦能量

  1、二进制加法基本指令(1)ADD指令格式:ADDDST,SRC该指令把源操作数(SRC)指向的数据与目的操作数(DST)相加后,将结果放到目的操作数(DST)中,所执行的操作:(DST)ß(SRC)...博文来自:的博客

  我是用StringBuilder做的,网上还有更简单的方法(用递归实现的,只有一行),不过我看不懂什么意思,暂时只会这个 /** *二进制加法,输入和输出都是字符串类型 *@parambin1 *@p...博文来自:u013086962的博客

  1.循环递归,并且当前的结果受前段时间的结果影响,不同样本间是有联系的以下是反向传播时对权重进行调整的推倒公式#coding:utf-8Createdon2017年3月18日#本项利用RNN递归...博文来自:qiujiahao123的博客

  使用循环神经网络(RNN)实现简易的二进制加法器利用python实现简易的循环神经网络,并在一个小demo(8比特二进制加法器)上进行了验证,激活函数为logistic函数,利用反向传播算法进行训练。...博文来自:Fly with python

  刚开始刷leetcode,第一道题是给两个二进制的字符串,求这两个二进制相加以后的和,输出当然也是二进制的格式了。以下是题目:/***Giventwobinarystrings,returntheir...博文来自:Dangerous的博客

  帐号相关流程注册范围n企业n政府n媒体n其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...博文来自:小雨同学的技术博客

  MATLAB编程题rn题目描述:从一个NxM的矩阵C中找出与1xM的矩阵P欧氏距离最小的某一行row,要求不能用循环!!!rn输入:矩阵C(NxM)、矩阵P(1xM)rn输出:rowrnrnrn解题思...博文来自:henryzhihua

  jquery/js实现一个网页同时调用多个倒计时(最新的)nn最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦!nnnn//jsn...博文来自:Websites

  由于CLion的工程都是基于CMake来构建的,因此导入第三方库就需要在CMake文件中进行配置。这里把利用CMake导入第三方库的过程记录下来。...博文来自:大迷毛的LALALAND

  卷积神经网络是深度学习的基础,但是学习CNN却不是那么简单,虽然网络上关于CNN的相关代码很多,比较经典的是tiny_cnn(C++)、DeepLearnToolbox(Matlab)等等,但通过C语...博文来自:tostq的专栏

  扫二维码关注,获取更多技术分享nnn 本文承接之前发布的博客《 微信支付V3微信公众号支付PHP教程/thinkPHP5公众号支付》必须阅读上篇文章后才可以阅读这篇文章。由于最近一段时间工作比较忙,...博文来自:Marswill

  一、定义状态(State)模式又称为状态对象模式(Pattern of Objects for State),状态模式是对象的行为模式。状态模式允许一个对象在其内部状态改变时改变其行为,用于解决系统中...博文来自:小小本科生成长之路

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗!nnDocker的三大核心概念:镜像、容器、仓库n镜像:类似虚拟机的镜像、用俗话说就是安装文件。n容器:类似一个轻量...博文来自:我走小路的博客

  本篇文章是根据我的上篇博客,给出的改进版,由于时间有限,仅做了一个简单的优化。相关文章:将excel导入数据库2018年4月1日,新增下载地址链接:点击打开源码下载地址十分抱歉,这个链接地址没有在这篇...博文来自:Lynn_Blog

  一、概述最近在springboot项目引入thymeleaf模板时,使用非严格标签时,运行会报错。默认thymeleaf模板对html5标签是严格检查的。二、在项目中加NekoHTML库在Maven中...博文来自:Luck_ZZ的博客

  本文介绍如何使用VS2015作为编译开发环境,调用OpenCV3.31和Qt5.9.1写图像处理的GUI。rn1.目录结构rn假设我们要创建一个名为VideoZoom的工程,那么首先按下图构建目录结构...博文来自:zhhp1001的博客

本文链接:http://williamzanker.com/yushiji/216.html