#noindex
특정한 입력 프로그램이 주어졌을 때, 튜링머신이 끝날지(정지할지, come to a halt)에 대한 [[결정,determination]].
4개 미만의 [[상태기계,state_machine]]에 대해선 풀 수 있다.
4개 [[상태,state]]에 대해선 아직.
5개 상태에 대해서도 아직. 거의 확실히 풀 수 없을 것으로 보임.
General TM이 정지할지 여부에 대한 문제는 undecidable. Alan_Turing이 증명.
(MathWorld)

'[[튜링_기계,Turing_machine]]와 입력이 주어져 있을 때 튜링 기계가 이 입력에 대해 유한시간 내에 계산을 끝내고 멈출 것인가 아니면 영원히 멈추지 않을 것인가'를 판별하는 문제
결론부터 말하면, 어떤 [[알고리듬,algorithm]]도 프로그램의 중단 여부를 판단할 수 없음. [[결정불가능성,undecidability]](opp. [[결정가능성,decidability]]) 문제임. (계산 불가능 혹은 결정 불가능)

알고리즘과 입력을 받아, 알고리즘이 언젠간 정지하고 결과를 출력할 지, 아니면 무한히 실행될 지를 결정하는 문제(see also [[결정문제,decision_problem]]). 이 문제를 해결하는 일반적인 방법은 없음. [[귀류법,proof_by_contradiction]]으로 증명함.
//from https://seungkwan.tistory.com/6 2.

tmp
{
https://everything2.com/title/halting-complete
}

MKLINK
[[정지,halting]]?
[[정지확률,halting_probability]] aka [[차이틴_상수,Chaitin_constant]] - writing; curr see Google:차이틴+상수
 관계는, curr see [[WpEn:Chaitin's_constant#Relationship_to_the_halting_problem]]

tmp links ko
https://m.blog.naver.com/ysyoo00/90031688544
[[모순,contradiction]].

Bmks ko
https://mathlyblog.wordpress.com/2015/12/29/정지-문제halting-problem/

----
AKA '''중단문제, 멈춤문제'''

tmp
{
totality_problem
totality problem: does a given machine halt for all its imputs?[* sic; from https://everything2.com/title/noncomputable]
이거 정지문제의 동의어? chk
Ggl:"totality problem"
}

https://johngrib.github.io/wiki/halting-problem/

http://www.aistudy.com/computer/halting_problem.htm
 [[결정문제,decision_problem]]의 일종임.

[[Namu:정지%20문제]]
 심지어 [[신탁기계,oracle_machine]]도 자기 자신의 정지문제를 풀 수 없다고.
 [[귀류법,proof_by_contradiction]] 사용한 증명 소개.


http://foldoc.org/halting+problem
[[WpKo:정지_문제]]
[[WpEn:Halting_problem]]
https://mathworld.wolfram.com/HaltingProblem.html
https://en.citizendium.org/wiki/Halting_problem
[[Wiki:HaltingProblem]]
https://brilliant.org/wiki/halting-problem/
https://everything2.com/title/Halting+problem
https://esolangs.org/wiki/Halting_problem

Up: [[문제,problem]] (curr. [[전산학,compsci#s-6]])