1、第4章馮.諾依曼計(jì)算機(jī)：機(jī)器級(jí)程序及其執(zhí)行諾依曼計(jì)算機(jī)：機(jī)器級(jí)程序及其執(zhí)行1、關(guān)于“圖靈機(jī)”，下列說(shuō)法不正確的是_____。(A)圖靈機(jī)給出的是計(jì)算機(jī)的理論模型；(B)圖靈機(jī)的狀態(tài)轉(zhuǎn)移函數(shù)，其實(shí)就是一條指令，即在q狀態(tài)下，當(dāng)輸入為X時(shí)，輸出為Y，讀寫(xiě)頭向右(R)、向左(L)移動(dòng)一格或不動(dòng)(N)，狀態(tài)變?yōu)閜；(C)圖靈機(jī)是一種離散的、有窮的、構(gòu)造性的問(wèn)題求解思路；(D)凡是能用算法方法解決的問(wèn)題也一定能用圖靈機(jī)解決；凡是圖靈機(jī)解決不了的問(wèn)

2、題人和算法也解決不了；(E)上述有不正確的。答案：E解釋?zhuān)罕绢}考核基本的圖靈機(jī)模型。20世紀(jì)30年代，圖靈提出了圖靈機(jī)模型，建立了指令、程序及通用機(jī)器執(zhí)行程序的理論模型，奠定了計(jì)算理論的基礎(chǔ)，因此(A)正確；選項(xiàng)(B)是圖靈機(jī)的五元組形式的指令集，是一個(gè)行動(dòng)集合，又稱(chēng)狀態(tài)轉(zhuǎn)移函數(shù)，因此正確；圖靈機(jī)是一種離散的、有窮的、構(gòu)造性的問(wèn)題求解思路，一個(gè)問(wèn)題的求解可以通過(guò)構(gòu)造其圖靈機(jī)（即算法和程序）來(lái)解決，因此(C)正確；(D)為圖靈可計(jì)算性問(wèn)題

3、，正確。綜上，本題答案為(E)。具體內(nèi)容請(qǐng)參考第四章視頻之“圖靈機(jī)的思想與模型簡(jiǎn)介”以及第四章課件。2、關(guān)于“圖靈機(jī)”和“計(jì)算”，下列說(shuō)法不正確的是_____。(A)計(jì)算就是對(duì)一條兩端可無(wú)限延長(zhǎng)的紙帶上的一串0和1，一步一步地執(zhí)行指令，經(jīng)過(guò)有限步驟后得到的一個(gè)滿(mǎn)足預(yù)先規(guī)定的符號(hào)串的變換過(guò)程；(B)“數(shù)據(jù)”可被制成一串0和1的紙帶送入機(jī)器中進(jìn)行自動(dòng)處理，被稱(chēng)為數(shù)據(jù)紙帶；處理數(shù)據(jù)的“指令”也可被制作成一串0和1的紙帶送入機(jī)器中，被稱(chēng)為程序紙

4、帶；機(jī)器一方面閱讀程序紙帶上的指令，并按照該指令對(duì)數(shù)據(jù)紙帶上的數(shù)據(jù)進(jìn)行變換處理。(C)計(jì)算機(jī)器可以這樣來(lái)制造：讀取程序紙帶上的指令，并按照該指令對(duì)數(shù)據(jù)紙帶上的數(shù)據(jù)做相應(yīng)的變換，這就是圖靈機(jī)的基本思想；(D)上述有不正確的。答案：D大學(xué)計(jì)算機(jī)計(jì)算思維練習(xí)題集當(dāng)遇到第一個(gè)0，將0轉(zhuǎn)換成X，然后向右移一位，進(jìn)入狀態(tài)S2，該狀態(tài)檢測(cè)下一位是否為1，當(dāng)不是的話，什么都不做，直接向右移一位，知道遇到第一個(gè)1，遇到以后，將1轉(zhuǎn)換成Y，向左移動(dòng)，進(jìn)入到

5、狀態(tài)S3，該狀態(tài)回溯0、1串，直到遇到X，然后指向在其右側(cè)的符號(hào)，返回到S1狀態(tài)。這個(gè)過(guò)程即為一個(gè)左側(cè)連續(xù)0的個(gè)數(shù)和右側(cè)連續(xù)1的個(gè)數(shù)相同的0、1串，每次都尋找排在最前面的一個(gè)0和一個(gè)1，將它們分別轉(zhuǎn)換成X，Y，直到所有的0和1轉(zhuǎn)換為X和Y。因此，答案(D)正確。具體內(nèi)容請(qǐng)參考第四章視頻之“圖靈機(jī)的思想與模型簡(jiǎn)介”以及第四章課件。4、下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個(gè)圖靈機(jī)，其字母集合為01XYB，其中B為空白字符；狀態(tài)集合S1，S2，S3，S

6、4，S5，S6，其中S1為起始狀態(tài)，S6為終止?fàn)顟B(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標(biāo)注的如表示輸入是in時(shí)，輸出out，向direction方向移動(dòng)一格，同時(shí)將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中inout均是字母集中的符號(hào)，direction可以為R(向右移動(dòng))、L(向左移動(dòng))、N(停留在原處)。該圖靈機(jī)的功能是_____。(A)識(shí)別是否如0101，01010101的0、1串，即一個(gè)0接續(xù)一個(gè)1，且0的個(gè)數(shù)和1的個(gè)數(shù)相同；(B)識(shí)別是否如000111