自动机之图灵机

本文概述

  • 图灵机的正式定义
图灵机由艾伦·图灵(Alan Turing)于1936年发明。它是一种接受设备,它接受由类型0语法生成的递归可枚举语言。
图灵机具有多种功能:
  1. 它具有一个外部存储器,可以记住任意长输入序列。
  2. 它具有无限的存储功能。
  3. 该模型具有可轻松读取磁带左侧或右侧输入的功能。
  4. 机器可以根据其输入产生一定的输出。有时可能需要使用相同的输入来生成输出。因此,在该机器中,输入和输出之间的区别已消除。因此,图灵机可以使用一组通用的字母。
图灵机的正式定义图灵机可以定义为7个组件的集合:
Q:状态的有限集合∑:输入符号的有限集合T:磁带符号q0:初始状态F:一组最终状态B:用作输入的结束标记的空白符号δ:过渡或映射功能。
映射功能显示了从有限自动机的状态和磁带上的输入符号到下一个状态,外部符号以及磁带头移动方向的映射。这被称为三重奏或图灵机程序。
(q0, a) → (q1, A, R)

这意味着在q0状态下,如果我们读取符号’ a’ ,它将进入状态q1,用X代替a并向右移动(R代表右)。
例:
为语言L = {0n1n}构造TM,其中n> = 1。
解:
我们已经通过PDA解决了这个问题。在PDA中,我们有一个堆栈来记住先前的符号。图灵机的主要优点是我们有一个可以向前或向后移动的磁带头,并且可以扫描输入的磁带。
我们将应用的简单逻辑是,读出A标记的每个“ 0”,然后与输入带一起向前移动,找出1将其转换为B。现在,对所有a和b重复此过程。
现在,我们将看到该图灵机在0011上的工作方式。

自动机之图灵机

文章图片
现在,我们将看到此图灵机如何在0011上工作。最初,状态为q0,并且将head指向0的方式是:
自动机之图灵机

文章图片
移动将为δ(q0,0)=δ(q1,A,R),这意味着它将进入状态q1,将0替换为A,并且磁头将向右移动为:
自动机之图灵机

文章图片
移动将为δ(q1,0)=δ(q1,0,R),这意味着它将不会更改任何符号,而是保持相同的状态并向右移动,如下所示:
自动机之图灵机

文章图片
该移动将为δ(q1,1)=δ(q2,B,L),这意味着它将进入状态q2,由B替换为1,并且头部将向左移动为:
自动机之图灵机

文章图片
现在,移动将为δ(q2,0)=δ(q2,0,L),这意味着它将不会更改任何符号,而是保持相同的状态并向左移动:
自动机之图灵机

文章图片
该移动将为δ(q2,A)=δ(q0,A,R),这意味着将进入状态q0,将A替换为A,并且头部将向右移动为:
自动机之图灵机

文章图片
该移动将为δ(q0,0)=δ(q1,A,R),这意味着它将进入状态q1,将0替换为A,并且磁头将向右移动为:
自动机之图灵机

文章图片
该移动将为δ(q1,B)=δ(q1,B,R),这意味着它将不会更改任何符号,而是保持相同的状态并向右移动,如下所示:
自动机之图灵机

文章图片
该移动将为δ(q1,1)=δ(q2,B,L),这意味着它将进入状态q2,由B替换为1,并且头部将向左移动为:
自动机之图灵机

文章图片
移动δ(q2,B)=(q2,B,L)表示将不更改任何符号,保持相同状态并向左移动,如下所示:
自动机之图灵机

文章图片
现在,紧接在B之前是A,这意味着所有0都由A卖出。因此,我们将向右移动以确保不存在1。移动将为δ(q2,A)=(q0,A,R),这意味着它将进入状态q0,将不更改任何符号,并向右移动为:
自动机之图灵机

文章图片
移动δ(q0,B)=(q3,B,R),这意味着它将进入状态q3,不会更改任何符号,并且向右移动为:
自动机之图灵机

文章图片
移动δ(q3,B)=(q3,B,R)表示它不会更改任何符号,而是保持相同的状态并向右移动,如下所示:
自动机之图灵机

文章图片
移动δ(q3,Δ)=(q4,Δ,R)表示将进入状态q4,这是HALT状态,而HALT状态始终是任何TM的接受状态。
自动机之图灵机

文章图片
【自动机之图灵机】相同的TM可用过渡图表示:

    推荐阅读