Simone
首先，什么叫做图灵机识别语言？并不是把一个文件输入到图灵机里就叫做图灵机识别这种语言。大家都知道图灵机是一种计算机器，输入一个字符串，可能进入接受状态、拒绝状态或者永不停机。 设M是一台图灵机 ，若在输入串S 上 M 运没派行后可进入接受状态并停机，则称 M 接受串S。M 所接受的所有字符串的集合称为M所识别的语言，简称M的语言，记作 L(M)。 请注意，语言L如果是图灵机M所识别的语言，则L中的差返字符串输入M，M将停机并进入接受状态。如果不是L中的字符串输入M，会是什么结果？只能有两种情况：M停机并进入拒绝状态，或者M不停机。 用图灵机解决的问题都是计算问题，就是一个有已知求未知的问题。你觉得数学中什么东西正是这个作用？是函数，简单的说就是y=f(x)。图灵机正好与可计算函数等价。现在就用这个例子说明求解y=f(x)是如何等价于一种图灵机识别的语言的： 一种语言L={
