http:^^www.cs.washington.edu^education^courses^322^96w^handout4^handout4.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 74 行

HTML
74 行
字号 
Date: Wed, 08 Jan 1997 20:50:03 GMTServer: NCSA/1.4.2Content-type: text/html<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN"><!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds ><HEAD><TITLE>The Halting Problem</TITLE></HEAD><BODY><meta name="description" value="The Halting Problem"><meta name="keywords" value="handout4"><meta name="resource-type" value="document"><meta name="distribution" value="global"><P> <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR><B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A><BR> <HR> <P><P><H1>The Halting Problem</H1><P><STRONG></STRONG><P><P><STRONG></STRONG><P><P>The halting problem is defined to be:<UL><LI>Input: Turing machine <b>M</b> and binary input <b>x</b>,<LI>Property: <b>M</b> halts on input <b>x</b>.</UL><P><b> Theorem:</b> The halting problem is undecidable.<P><b> Proof:</b>  The proof is by contradiction.  Suppose that the halting problem is decidable.Then there must be a Turing machine <b>H</b> with theproperty that <b>H</b> halts on all inputs, and accepts <IMG  ALIGN=MIDDLE ALT="" SRC="img1.gif"> if and only if <b>M</b> halts on input <b>x</b>.(Recall that <IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif"> is the binary representation of the Turing machine <b>M</b>.)<P>We define a new Turing machine <b>D</b> which does the following on inputs ofthe form <IMG  ALIGN=MIDDLE ALT="" SRC="img3.gif">.<OL><LI>Copy the input <IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif"> to form the string <IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif">.<LI>Run <b>H</b> on the input <IMG  ALIGN=MIDDLE ALT="" SRC="img6.gif">.<OL><LI>If <b>H</b> halts without accepting then <b>D</b> halts.<LI>If <b>H</b> halts and accepts then <b>D</b> simply loops forever.</OL></OL><P>There are two possibilities, <b>D</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif"> or <b>D</b> doesnot halt on input <IMG  ALIGN=MIDDLE ALT="" SRC="img8.gif">.We will come to a contradiction in both cases.<P>If  <b>D</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif">, then by the definition of <b>H</b>,<b>H</b> accepts<IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">.  By the definition of <b>D</b>, <b>D</b> does not halt on input <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif">.<P>If  <b>D</b> does not halt on input <IMG  ALIGN=MIDDLE ALT="" SRC="img12.gif">, then by the definition of <b>H</b>,<b>H</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img13.gif"> without accepting.  By the definition of <b>D</b>, <b>D</b> halts on input <IMG  ALIGN=MIDDLE ALT="" SRC="img14.gif">.<P><BR> <HR><UL> <LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A></UL><BR> <HR><P><ADDRESS><I>James Fix <BR>Tue Mar 12 11:18:16 PST 1996</I></ADDRESS></BODY>

http:^^www.cs.washington.edu^education^courses^322^96w^handout4^handout4.html - 源码说明

本页面展示了「This data set contains WWW-pages collected from computer science departments of various universities」中的 http:^^www.cs.washington.edu^education^courses^322^96w^handout4^handout4.html 源码文件，采用 HTML 编程语言编写，共 74 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫开发者社区收录了大量与数据集相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?