2. 计算机
  3. The　Turing　machine　is　an　abstract(71)of　computer　execution　and　storage　introduced　in　1936　by　Alan　Turing　to　give　a　mathematicall

The　Turing　machine　is　an　abstract(71)of　computer　execution　and　storage　introduced　in　1936　by　Alan　Turing　to　give　a　mathematicall

admin2009-02-15  38
问题 The　Turing　machine　is　an　abstract(71)of　computer　execution　and　storage　introduced　in　1936　by　Alan　Turing　to　give　a　mathematically　precise　definition　of(72).　or　’mechanical　procedure’.　As　such　it　is　still　widely　used　in　theoretical　computer　science,　especially　in(73)theory　and　the　theory　of　computation.　The　thesis　that　states　that　Turing　machines　indeed　capture　the　informal　notion　of　effective　or　mechanical　method　in　logic　and　mathematics　is　known　as　Turing’s　thesis.
　　　Every　Turing　machine　computes　a　certain(74)partial　function　over　the　strings　over　its　alphabet.　In　that　sense　it　behaves　like　a　computer　with　a　fixed　program.　However,　as　Alan　luring　already　described,　we　can　encode　the　action　table　of　every　Turing　machine　in　a　string.　Thus　we　might　try　to　construct　a　Turing　machine　that　expects　on　its　tape　a　string　describing　an　action　table　followed　by　a　string　describing　the　input　tape,　and　then　computes　the　tape　that　the　encoded　Turing　machine　would　have　computed.　As　Turing　showed,　such　a　luring　machine　is　indeed　possible　and　since　it　is　able　to　simulate　any　other　Turing　machine　it　is　called　a(75)Turing　machine.
　　　A　universal　Turing　machine　is　Turing　complete.　It　can　calculate　any　recursive　function,　decide　any　recursive　language,　and　accept　any　recursively　enumerable　language.　According　to　the　Church-Turing　thesis,　the　problems　solvable　by　a　universal　Turing　machine　are　exactly　those　problems　solvable　by　an　algorithm　or　an　effective　method　of　computation,　for　any　reasonable　definition　of　those　terms.
选项 A、intricacy
B、complexity
C、complicacy
D、difficulty
答案B
解析
转载请注明原文地址:https://kaotiyun.com/show/nHxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)