您现在的位置是:首页 > 正文

Halting problem(停机问题)

2024-04-01 03:31:45阅读 3

1.Introduction

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program’s execution; it can take arbitrarily long, and use arbitrarily as much storage space, before halting. The question is simply whether the given program will ever halt on a particular input.

停机问题是用于判断这个程序是否会自动退出或者会一直运行下去。例如一个死循环,在内存没有限制的条件下,这个程序不能自动退出,即它会一直运行下去。对于普通正常的程序,举一个非常简单的例子,如helloworld,在运行结束后会自动退出。你会发现, 这是一个很值得研究的问题。因为计算机的资源是有限的,如果一个程序不会自动停止,它便会消耗大量资源与时间,大大降低了效率。假如我们能够设计一个范型算法,适用于对所有程序进行测试,对不能自动退出的程序发出警告,那么这便会大大提高我们的工作效率。可惜的是,目前并不存在这种算法。

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.

对于这个问题,图灵本人便做过验证,发现并不存在一种通用的算法能实现这一功能,他认为这是图灵机上仍不能解决的一个问题,同时他也给出了证明:Halting_problem-Sketch_of_proof

更多的细节详见:Halting problem

那么,我们能不能通过一些条件限制,如时间限制,内存限制来大约估计程序是否会停机?

显然是可以的。虽然停机问题是无法解决的,但是我们可以通过条件限制,即根据它的趋势来预测是否会出现停机,以达到我们测试的目的。

下面我通过讲解一道例题,帮助读者进一步了解停机问题!

2.Example

In this project, the rule is:
TIME LIMIT: 1 second
MEMORY LIMIT: 8 MB
FUNCTION INPUT: 5

What should you do in this project:
1. Define the function “Decide()”;
2. In “Decide()”, different functions will be as input;
3. The program you write should stop the unstopable function;
4. The program you write should run through the stopable function;

Simple

网站文章

  • 修改 navigator.platform 的值

    // ==UserScript== // @name 修改 navigator.platform 的值 // @namespace http://tampermonkey.net/ // @versi...

    2024-04-01 03:31:02
  • php require_once 绝对路径,关于php:使用require_once的路径错误

    我在尝试使用require_once时遇到问题。我指定了错误的路径,但找不到解决方案。我有一个名为header.php的文件,该文件通过使用require_once包括两个文件:functions.p...

    2024-04-01 03:30:54
  • Centos6.5 安装Composer

    对于现代语言而言,包管理器基本上是标配。Java有Maven,Python有pip,Ruby有gem,Nodejs有npm。PHP的则是PEAR,不过PEAR坑不少:依赖处理容易出问题配置非常复杂难用的命令行接口好在我们有Composer,PHP依赖管理的利器。它是开源的,使用起来也很简单,提交自己的包也很容易。安装ComposerComposer需要PHP 5.3.2+才能运

    2024-04-01 03:30:46
  • 南农计算机考研真题,2021南京农业大学考研历年真题

    该楼层疑似违规已被系统折叠隐藏此楼查看此楼来源:http://fangcai.100xuexi.com/Ebook/DigitalLibrary/BookNew.aspx?BookName=%u535...

    2024-04-01 03:30:03
  • 如何在整数补0/保留数位

    如何在整数补0/保留数位 学校居然断网,太过分了.... 记录一下怎么在整数部分前加0,用的代码是 cout<<<

    2024-04-01 03:29:54
  • Tez引擎

    Tez计算框架采用DAG,最大的改进在于避免中间数据集从内存写入磁盘的操作,同时减少了中间作业集,增加了硬件资源利用率。

    2024-04-01 03:29:45
  • 《BI项目笔记》创建标准维度、维度自定义层次结构

    《BI项目笔记》创建标准维度、维度自定义层次结构

    《BI项目笔记》创建标准维度、维度自定义层次结构 原文:《BI项目笔记》创建标准维度、维度自定义层次结构 posted on 2014-12-02 08:57 NET未来之路 阅读(...) 评论(...) 编辑 收藏 var a...

    2024-04-01 03:29:02
  • Springboot中如何打印sql信息和sql参数信息呢?

    Springboot中打印sql信息和sql参数信息的方法分享

    2024-04-01 03:28:57
  • 前端 面经/编码规范/教程/安装总结

    文章目录面经编码规范学习教程最近梳理了一些前端可能用到的教程:面经震惊!前端300基础面试题+答案、分类学习整理(良心制作)持续更新很全面的vue面试题总结编码规范15 Rules For Writing Clean JavaScript学习教程ES6 入门教程vue官方文档vue收藏!工作中Git使用实践和常用命令流程合集ElementUI组件iview...

    2024-04-01 03:28:50
  • 企业项目实战k8s篇(十九)K8s高可用+负载均衡集群

    企业项目实战k8s篇(十九)K8s高可用+负载均衡集群

    K8s高可用+负载均衡集群一.K8s高可用+负载均衡集群概述二.K8s高可用集群部署1.pacemaker+haproxy的高可用+负载均衡部署2.k8s高可用集群部署一.K8s高可用+负载均衡集群概...

    2024-04-01 03:28:42