k带图灵机的空间复杂性S（n）是指（）

A、k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最大方格数

B、k带图灵机处理所有长度为n的输入时，在k条带上所使用过的方格数的总和

C、k带图灵机处理所有长度为n的输入时，在k条带上所使用过的平均方格数

D、k带图灵机处理所有长度为n的输入时，在某条带上所使用过的最小方格数

相关问题推荐

• 图灵在密码方面取得的成就______。他发明了“图灵机”。虽然这个机器当时是为战争服务的，不过，在人工智能的发展历史中，却是______的一个事件。
  A.可望而不可即，开天辟地
  B.可望而不可及，开天辟地
  C.可望而不可及，开天劈地
  D.可望而不可即，开天劈地

  查看答案

• 关于“图灵机”和“计算”，下列说法不正确的是_____。

  (A)计算就是对一条两端可无限延长的纸带上的一串0和1，一步一步地执行指令，经过有限步骤后得到的一个满足预先规定的符号串的变换过程;

  (B)“数据”可被制成一串0和1的纸带送入机器中进行自动处理，被称为数据纸带;处理数据的“指令”也可被制作成一串0和1的纸带送入机器中，被称为程序纸带;机器一方面阅读程序纸带上的指令，并按照该指令对数据纸带上的数据进行变换处理。

  (C)计算机器可以这样来制造：读取程序纸带上的指令，并按照该指令对数据纸带上的数据做相应的变换，这就是图灵机的基本思想;

  (D)上述有不正确的。

  查看答案
• 下列关于图灵机的说法错误的是（）
  A.图灵机是一台由真空管为基本元件的早期计算机B.现代计算机的功能不可能超越图灵机C.只有图灵机能解决的计算问题，实际计算机才能解决D.图灵机不可以计算的问题，现代计算机也不能计算

  查看答案

• Chomsky定义的四种形式语言文法中，2型语言可由()识别。

  A、短语结构文法

  B、前后文无关文法

  C、前后文有关文法

  D、正规文法

  E、图灵机

  F、有限自动机

  G、下推自动机

  查看答案