【正文】 大學(xué)計(jì)算機(jī)計(jì)算思維練習(xí)題集第4章 ：機(jī)器級(jí)程序及其執(zhí)行 關(guān)于“圖靈機(jī)”，下列說法不正確的是_____。 (A)圖靈機(jī)給出的是計(jì)算機(jī)的理論模型；(B)圖靈機(jī)的狀態(tài)轉(zhuǎn)移函數(shù)q, X, Y, R(或L或N), p，其實(shí)就是一條指令，即在q狀態(tài)下，當(dāng)輸入為X時(shí)，輸出為Y，讀寫頭向右(R)、向左(L)移動(dòng)一格或不動(dòng)(N)，狀態(tài)變?yōu)閜； (C)圖靈機(jī)是一種離散的、有窮的、構(gòu)造性的問題求解思路； (D)凡是能用算法方法解決的問題也一定能用圖靈機(jī)解決；凡是圖靈機(jī)解決不了的問題人和算法也解決不了； (E)上述有不正確的。答案：E解釋：本題考核基本的圖靈機(jī)模型。20世紀(jì)30年代，圖靈提出了圖靈機(jī)模型，建立了指令、程序及通用機(jī)器執(zhí)行程序的理論模型，奠定了計(jì)算理論的基礎(chǔ)，因此(A)正確；選項(xiàng)(B)是圖靈機(jī)的五元組形式的指令集，是一個(gè)行動(dòng)集合，又稱狀態(tài)轉(zhuǎn)移函數(shù)，因此正確；圖靈機(jī)是一種離散的、有窮的、構(gòu)造性的問題求解思路，一個(gè)問題的求解可以通過構(gòu)造其圖靈機(jī)（即算法和程序）來解決，因此(C)正確；(D)為圖靈可計(jì)算性問題，正確。綜上，本題答案為(E)。具體內(nèi)容請(qǐng)參考第四章視頻之“圖靈機(jī)的思想與模型簡(jiǎn)介”以及第四章課件。關(guān)于“圖靈機(jī)”和“計(jì)算”，下列說法不正確的是_____。(A)計(jì)算就是對(duì)一條兩端可無限延長(zhǎng)的紙帶上的一串0和1，一步一步地執(zhí)行指令，經(jīng)過有限步驟后得到的一個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過程；(B)“數(shù)據(jù)”可被制成一串0和1的紙帶送入機(jī)器中進(jìn)行自動(dòng)處理，被稱為數(shù)據(jù)紙帶；處理數(shù)據(jù)的“指令”也可被制作成一串0和1的紙帶送入機(jī)器中，被稱為程序紙帶；機(jī)器一方面閱讀程序紙帶上的指令，并按照該指令對(duì)數(shù)據(jù)紙帶上的數(shù)據(jù)進(jìn)行變換處理。 (C)計(jì)算機(jī)器可以這樣來制造：讀取程序紙帶上的指令，并按照該指令對(duì)數(shù)據(jù)紙帶上的數(shù)據(jù)做相應(yīng)的變換，這就是圖靈機(jī)的基本思想； (D)上述有不正確的。答案：D解釋：本題考核對(duì)圖靈機(jī)思想的理解。(A)(B)(C)均敘述正確，(D)錯(cuò)誤。具體內(nèi)容請(qǐng)參考第四章視頻之“圖靈機(jī)的思想與模型簡(jiǎn)介”以及第四章課件。下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個(gè)圖靈機(jī)，其字母集合為{0,1,X,Y,B}，其中B為空白字符；狀態(tài)集合{S1，S2，S3，S4，S5}，其中S1為起始狀態(tài)，S5為終止?fàn)顟B(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標(biāo)注的如in, out, direction表示輸入是in時(shí)，輸出out，向direction方向移動(dòng)一格，同時(shí)將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號(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，00001111的0、1串，即左側(cè)連續(xù)0的個(gè)數(shù)和右側(cè)連續(xù)1的個(gè)數(shù)相同的0、1串；(C)將形如0101，01010101的0、1串，即一個(gè)0接續(xù)一個(gè)1，且0的個(gè)數(shù)和1的個(gè)數(shù)相同， 轉(zhuǎn)換為XYXY， XYXYXYXY的形式； (D)將形如000111，00001111的0、1串，即左側(cè)連續(xù)0的個(gè)數(shù)和右側(cè)連續(xù)1的個(gè)數(shù)相同的0、1串轉(zhuǎn)換為XXXYYY， XXXXYYYY的形式。答案：D解釋：本題考核圖靈機(jī)模型及其應(yīng)用。根據(jù)本題中in, out, direction的描述及狀態(tài)轉(zhuǎn)移圖，可以看到該圖靈機(jī)是將一個(gè)0、1串中的0轉(zhuǎn)換成X，1轉(zhuǎn)換成Y。接著，具體來看SSS3的轉(zhuǎn)移，一個(gè)串從S1開始，當(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)入到狀態(tài)S3，該狀態(tài)回溯0、1串，直到遇到X，然后指向在其右側(cè)的符號(hào)，返回到S1狀態(tài)。這個(gè)過程即為一個(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)介”以及第四章課件。下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個(gè)圖靈機(jī)，其字母集合為{0,1,X,Y,B}，其中B為空白字符；狀態(tài)集合{S1，S2，S3，S4，S5，S6}，其中S1為起始狀態(tài)，S6為終止?fàn)顟B(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標(biāo)注的如in, out, direction表示輸入是in時(shí)，輸出out，向direction方向移動(dòng)一格，同時(shí)將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號(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，00001111的0、1串，即左側(cè)連續(xù)0的個(gè)數(shù)和右側(cè)連續(xù)1的個(gè)數(shù)相同的0、1串；(C)將形如0101，01010101的0、1串，即一個(gè)0接續(xù)一個(gè)1，且0的個(gè)數(shù)和1的個(gè)數(shù)相同， 轉(zhuǎn)換為XYXY， XYXYXYXY的形式； (D)將形如000111，00001111的0、1串，即左側(cè)連續(xù)0的個(gè)數(shù)和右側(cè)連續(xù)1的個(gè)數(shù)相同的0、1串轉(zhuǎn)換為XXXYYY， XXXXYYYY的形式。答案：B解釋：本題考核對(duì)圖靈機(jī)思想的理解。該圖靈機(jī)由上題衍生出來，即類似(A)(C)中的間隔字符串無法通過S4，而類似(B)(D)中的字符串可以運(yùn)行至S4將0、1串變更為X、Y串，但在S5狀態(tài)中圖靈機(jī)又將X、Y串變回0、1串，因此該圖靈機(jī)不是用來轉(zhuǎn)換字串的，該圖靈機(jī)是用來檢驗(yàn)字串的，因此(B)正確。具體內(nèi)容請(qǐng)參考第四章視頻之“圖靈機(jī)的思想與模型簡(jiǎn)介”以及第四章課件。下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個(gè)圖靈機(jī)，其字母集合為{V，C，+，=，“空格”，；}；狀態(tài)集合{S1，S2，S3，S4，S5，S6，S7}，其中S1為起始狀態(tài)，S7為終止?fàn)顟B(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標(biāo)注的如in, out, direction表示輸入是in時(shí)，輸出out，向direction方向移動(dòng)一格，同時(shí)將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號(hào)，null表示什么也不寫，direction可以為R(向右移動(dòng))、L(向左移動(dòng))、N(停留在原處)。該圖靈機(jī)的功能是_____。 (A)能夠識(shí)別“V=C+C；”形式的符號(hào)串； (B)能夠識(shí)別“V=C；”形式的符號(hào)串；(C)能夠?qū)⒎?hào)串中的空格去除掉； (D)上述全部能夠識(shí)別。答案：D解釋：本題考核圖靈機(jī)模型及其應(yīng)用。選項(xiàng)(A)的狀態(tài)轉(zhuǎn)移順序?yàn)镾1S2S3S4S5S6S7；選項(xiàng)(B)為S1S2S3S4S7；選項(xiàng)(C)從每個(gè)狀態(tài)中可以看出，遇到空格不做工作，直接指向下一符號(hào)，即跳過空格。因此選項(xiàng)(A)(B)(C)均正確，本題答案為(D)。具體內(nèi)容請(qǐng)參考第四章視頻之“圖靈機(jī)的思想與模型簡(jiǎn)介”以及第四章課件。下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個(gè)圖靈機(jī)，其字母集合為{V，C，+，=，“空格”，；}；狀態(tài)集合{S