정지문제,halting_problem

특정한 입력 프로그램이 주어졌을 때, 튜링머신이 끝날지(정지할지, 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