(MIT6.045)自动机、可计算性和复杂性-图灵机

news/2023/12/9 13:31:40

有穷自动机(FA)对有限存储量设备是比较好的模型,下推自动机对无限存储设备是较好的模型(但是其存储只能用后进先出的栈模式来使用。)这两个模型过于局限,不能作为通用模型。

图灵机

和FA相似,但是图灵机有无限的存储。图灵机可以作实际计算机做的所有事情。但是也有图灵机解不了的事情(这些问题就超越了计算的理论极限。)

图灵机模型使用无限长度的纸带作为无限存储,并且它具有可以读取,写入和移动磁带的读/写头。

开始时,纸带上只有输入字符串,纸带的其他部分都是空的。图灵机有读写头,可以在带子上左右移动。如果需要保存信息,它可能会将该信息写入纸带。要阅读书面消息,它可能会将读/写头移回消息所在的纸带位置。

机器不断计算,直到产生输出。机器事先设置为两种状态:接受或拒绝。如果进入这些状态中的任何一种,则会产生输出接受或拒绝。如果未进入任何接受或拒绝状态,则执行将继续且永不停止。

在这里插入图片描述

有穷自动机(FA)和图灵机的区别:

  1. 图灵机的带子可以写也可以读
  2. 读写头可以左右移动
  3. 带子无限长
  4. 在状态处于接受和拒绝时将立即停机

图灵机的形式定义

在这里插入图片描述
图灵机的输入是有限长的。

图灵机在很多情况下是“针对某个算法的”图灵机。根据问题和算法的不同,会出现解决各种问题的图灵机。

这里的算法,意味着状态转移函数 δ \delta δ的不同。

状态转移函数 δ \delta δ是映射:
(当前状态,纸带当前位置字母) → \rightarrow (下一个状态,纸带字母改写结果,读写头移动方向)

图灵机的格局:包括现在读写头的位置、当前的状态、当前纸带的内容。

我们可以基于格局对图灵机的计算进行形式化。如果图灵机可以合法地从格局C1一步到格局C2,则称格局C1产生格局C2。

起始格局(读写头在纸带最左端)、接受格局(接受状态)、拒绝格局(拒绝状态)。

图灵机M接受的所有字符串全体成为M的语言,记为L(M)。

定义: 如有图灵机识别(接受)一个语言,那么称此语言是图灵可识别的。

图灵机在跑的时候,可能在有限步后接受或者拒绝,也可能无限地运行下去而不停机(称为循环,但是和for/while之类的循环不同,它只是不停机)

于是我们更喜欢对所有输入都停机的图灵机,称其为判定器(不会陷入循环的图灵机)。

定义: 语言是可判定的,如果有图灵机判定它。

可判定 => 可识别,但是可识别不一定意味着可判定。

可判定和可识别性的区别。比如,给定一个单变量多项式 p p p,计算它有无整数根。那么图灵机可依次考察0,1,-1,2,-2,…来找整数根。这意味着,它确实可以识别出整数根,但是没有整数根的话,这个算法就得无休无止地跑。

图灵机的变形

  1. 多带图灵机:有多个带子,每个带子有自己的读写头。起始输入在第一个带子上。可以通过对纸带进行映射完成等价性证明。
  2. 非确定性图灵机:可以类比DFA和NFA。等价性的证明可以考虑对格局变化的广度优先搜索。
  3. 枚举器:带有打印机的图灵机。枚举器就是不断地输出语言中的所有串。

计算模型之间的普遍等价性

无限制访问无限的存储器,有这个特点的模型在计算能力上都是等价的,只需要满足一些合理的必要条件。

什么是算法:Church - Turing 论题

这两个人给出了算法的定义。其中,Church给出了 λ \lambda λ演算方法,Turing给出了图灵机。这两个定义是等价的。

在接下来的内容中,我们不去思考图灵机的基本构建,可以直接认为算法能用图灵机实现。

算法的可判定性问题

可判定语言

在这里插入图片描述

停机问题

有一些问题是计算机不能解(不可判定)的。

典型的例子是:给定一个图灵机和一个串,判断图灵机是否接受这个串。这个问题是不可判定的。

首先,这个问题是可以识别的。我们只需要模拟这个图灵机的状态演变。
这么做的话,确实可以把接受、拒绝态完成。问题是,如果进入循环,他就不停机了。如果它知道自己不停机,那么它可以拒绝串。问题是它不知道

这样的模拟用图灵机称为通用图灵机,可以模拟任何其他图灵机的行为。

集合的势(元素个数)

对于有限元素的集合,很容易判断他们的元素个数(称为势)是否相等。显然,3元素集的元素个数小于5元素集。

对于无限元素集,通过能否构造双射判断是否等势。

比如,整数集和有理数集等势,记其势为 ℵ 0 \aleph_0 0

实数集和有理数集不等势,记其势为 ℵ \aleph

2 ℵ 0 = ℵ 2^{\aleph_0} = \aleph 20=。其证明思路是考虑区间[0,1)中所有数的二进制编码。

通过幂的构造方式,可以证明没有最大的势。此即,假设集合A的势为 c c c,则 2 c > c 2^c > c 2c>c

推论: 存在语言不是图灵可识别的。

证明. 所有图灵机构成的集合是可数的。在这里插入图片描述
或者可以考虑给图灵机进行序列化,具体地,对七元组里的东西进行序列化,可以得到图灵机的编码(有限长度编码)。它是二进制自然数的子集。

但是,语言数是不可数的,因为 2 ℵ 0 = ℵ 2^{\aleph_0} = \aleph 20=

停机问题是不可判定的

首先,定义停机问题
A T M = { < M , w > ∣ M 为图灵机, M 接受 w } A_{TM} = \{<M, w> | M为图灵机,M接受w\} ATM={<M,w>M为图灵机,M接受w}
其中, < > <> <>代表某种编码。

这个问题是不可判定的。

证明 假设可判定,则存在图灵机 H H H可以判定 A T M A_{TM} ATM。此即
H ( < M , w > ) = a c c e p t , M H(<M, w>) = accept,M H(<M,w>)=acceptM accepts w w w
H ( < M , w > ) = r e j e c t , M H(<M, w>) = reject,M H(<M,w>)=rejectM rejects w w w

构造一个新的图灵机 D D D,它包含了 H H H的逻辑。具体地, D D D的输入为图灵机的编码 < M > <M> <M>
D ( < M > ) = a c c e p t D(<M>) = accept D(<M>)=accept, if H ( < M , < M > > ) = r e j e c t H(<M, <M>>) = reject H(<M,<M>>)=reject
D ( < M > ) = r e j e c t D(<M>) = reject D(<M>)=reject, if H ( < M , < M > > ) = a c c e p t H(<M, <M>>) = accept H(<M,<M>>)=accept

于是当M=D时即为矛盾。

注. 这个做法就像罗素的理发师悖论。理发师说:“我给且仅给不给自己理发的人理发”。于是这个理发师如果不给自己理发,那么他就给自己理发。如果他给自己理发,那么他不给自己理发。

一个图灵不可识别语言

**定理. **一个语言是可判定的,当且仅当它是图灵可识别的,也是补图灵可识别的(补集也是图灵可识别的)。

这就把所有循环的情况排除掉了。证明思路是,考虑用两个图灵机并行地判定语言集和其补。

于是,停机问题的补不是图灵可识别的。

可归约性

略,准备看看P和NP问题之后再回来补…


http://www.ppmy.cn/news/299069.html

相关文章

如何使用AI帮你制作PPT

一&#xff1a;前言 ChatGPT&#xff1a;智能AI助你畅聊天地 在现代人日益忙碌的生活中&#xff0c;难免需要一些轻松愉快的聊天来放松身心。而现在&#xff0c;有了 ChatGPT&#xff0c;轻松愉快的聊天变得更加智能、有趣且不受时间、地点限制&#xff01; 什么是 ChatGPT&…

realme真我gt能升级鸿蒙系统吗,realme真我GT Neo专为学生党打造,堪称性价比之王...

realme 真我 GT Neo 于上月31日举行了发布会&#xff0c;于4月8日零点正式开售。realme GT Neo首发搭载天玑1200旗舰芯片、120Hz电竞屏等&#xff0c;12GB256GB 版本仅售2299 元。天玑1200性能强劲&#xff0c;真我GT Neo可谓是两千元档最强性能旗舰手机&#xff0c;学生党入手…

搭载1亿像素相机,小米新品手机再成“性价比之王”

小米集团旗下品牌Redmi再度发布多款“性价比之王”手机新品。11月26日&#xff0c;小米发布Redmi Note9系列的Note9 Pro、Note9 5G和Note9 4G三款手机新品&#xff0c;三款手机价格均位于“千元档”甚至低于千元&#xff0c;再度成为市场上同价位机型中的“性价比之王”。对此&…

真无线蓝牙耳机推荐,千元以下蓝牙耳机性价比之王

说到蓝牙耳机&#xff0c;首先想到的就是它的便携和方便优势&#xff0c;随着近年来蓝牙技术的进步&#xff0c;蓝牙耳机在各方面都得到很大突出&#xff0c;作为一个数码爱好者&#xff0c;我几乎深入体验过市面上绝大部分的蓝牙耳机产品&#xff0c;今天就通过这篇文章&#…

代码随想录算法训练营第四十八天|打家劫舍专题

目录 LeeCode 198.打家劫舍 LeeCode 213.打家劫舍II LeeCode 337.打家劫舍 III LeeCode 198.打家劫舍 198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09; 动归五部曲&#xff1a; 1.确定dp数组及下标含义: dp[i]: 考虑下标i&#xff08;包括i&#xff09;以内的房屋…

深度学习训练营之优化器对比

深度学习训练营之优化器对比 原文链接环境介绍前置工作设置GPU 数据处理导入数据数据集处理数据集可视化 模型构造模型训练结果可视化 原文链接 &#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f366; 参考文章&#xff1a;365天深度学习训练营…

【计算思维题】少儿编程 蓝桥杯青少组计算思维 数学逻辑思维真题详细解析第8套

少儿编程 蓝桥杯青少组计算思维题真题及解析第8套 1、下列哪个选项填到填到下图空缺处最合适 A、 B、 C、 D、 答案:D 考点分析:主要考查小朋友们的观察能力,从给定的图中可以看到,图中的线条都是有实现和虚

【学习笔记】NOI 模拟赛 t3 point

点这里看题目 考场上也没想到这道 t 3 t3 t3竟是整场比赛最可做的一道题。但是拿了全场最高的部分分&#xff0c;这是好的。 唉&#xff0c;学了插头 d p dp dp但是却无法将其运用&#xff0c;我真傻&#xff0c;真的。 部分分已经很好的提示了这道题的正解是状压。先考虑 d…

一键生成代码

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…

零基础学网络安全的心得

我的学习心得&#xff0c;我认为能不能自学成功的要素有两点。 第一点就是自身的问题&#xff0c;虽然想要转行学习安全的人很多&#xff0c;但是非常强烈的想要转行学好的人是小部分。而大部分人只是抱着试试的心态来学习安全&#xff0c;这是完全不可能的。 所以能不能学成并…

3d vr 电影资源

https://t.me/s/VR3ddyISO

html5是否支持webvr,安卓版Chrome浏览器正式支持WebVR,VR看片更加方便!

你现在的位置: 首页 > VR > VR新闻 之前POPPUR为大家介绍过SVRF Tabs应用&#xff0c;各位在下载该插件之后&#xff0c;在Chrome 浏览器上建立新标签页时就可以欣赏全景图片&#xff0c;不过这和真正的VR浏览还有点距离。今天Chrome 安卓版进行了重大更新&#xff0c;各…

VR(手机)性能设计与优化(一) 总体思路

简单来讲&#xff0c;我们可以将VR系统分成硬件系统和软件系统两部分&#xff08;所有的电子设备基本都可以这么划分&#xff0c;包括手机&VR&电视&车机等&#xff09;&#xff0c;系统的性能与这两部分都是密不可分的。看到见摸得着的部分是硬件&#xff0c;基于硬…

vr片源免费网址_手机玩VR,你还可以这样做

因为片源的缺乏&#xff0c;3D电视逐渐淡出人们的视野。要想体验3D&#xff0c;更多时候只能到电影院中去占座。 而近年来&#xff0c;出现于上世纪的VR技术得到不断发展&#xff0c;但一度火热的宣传又在慢慢地降温。同样因为片源的原因&#xff0c;似乎VR被人们慢慢地冷落。 …

深度解读 | VR中的See-Through技术

近年来&#xff0c;虚拟现实&#xff08;VR&#xff09;行业迎来了爆发式增长&#xff0c;其消费级别的量产产品&#xff0c;目前已做到近千万级别的年销量。与此同时&#xff0c;VR行业不论是上游基础硬件还是下游软件生态都在迅速发展。 增强现实&#xff08;AR&#xff09;…

NVIDIA全息VR显示专利:内含多种光学方案

近期&#xff0c;USPTO公布了两项来自NVIDIA的新专利&#xff0c;这两项专利都与全息VR显示方案相关&#xff0c;编号分别为US20220334395 A1和US20220334392 A1。两项专利均来自同一个研发团队&#xff0c;发明者包括Jonghyun Kim&#xff0c;Ward Lopes、David Patrick Luebk…

VR行业的发展现状和前景

5G技术的应用推广&#xff0c;加速推动虚拟现实不断发展和完善&#xff0c;VR产业迅速在各个领域和行业都得到广泛应用&#xff0c;最好直观的感受就是知觉体验得到了良好的增强作用。本文的主要内容是简单概括VR技术的发展现状和发展前景。 一、VR技术以及现状 1.VR技术的基本…

VR技术分享交流

VR技术分享交流 虚拟现实(virtual reality,简称VR)是利用电脑模拟产生一个三维空间的虚拟世界&#xff0c;提供用户关于视觉等感官的模拟&#xff0c;让用户感觉仿佛身历其境&#xff0c;可以及时、没有限制地观察三维空间内的事物。用户进行位置移动时&#xff0c;电脑可以立…

VR入门

入门指南 本文档介绍如何使用实验性的 Cardboard SDK for Android 创建您自己的虚拟实境 (VR) 体验。 Android 演示版应用&#xff1a;Treasure Hunt 本教程中的代码示例摘自“Treasure Hunt”Android 演示版应用。 Cardboard 是一个简单的设备&#xff0c;可让智能手机发挥…

vr全景创业大概要投资多少

VR全景相较于传统展示形式更加直观便捷&#xff0c;应用广泛&#xff0c;可以在VR全景作品中任意植入多种传统广告及相关营销功能&#xff0c; 像餐饮、娱乐、酒店、房产、汽车、商场、学校、医院、工厂、物流、婚庆、景区、政府机关、施工项目等等都可以利用VR全景的形式&…
最新文章