현장에서 중단 문제가 발생한 적이 언제입니까?

현장에서 중단 문제가 발생한 적이 언제입니까?

---

현장에서 중단 문제 를 개인적으로 접한 적이 언제 입니까? 이것은 동료 / 상사가 계산의 근본적인 한계를 위반하는 솔루션을 제안했을 때 또는 해결하려는 문제가 실제로 해결 불가능하다는 것을 스스로 깨달았을 때일 수 있습니다.

내가 가장 최근에 생각 해낸 것은 타입 체커를 공부할 때였습니다. 우리 수업에서는 완벽한 유형 검사기 (유형 오류없이 실행되는 모든 프로그램을 허용하고 유형 오류로 실행되는 모든 프로그램을 거부하는)를 작성하는 것이 불가능하다는 것을 깨달았습니다. 이것이 실제로 중지 문제를 해결하기 때문입니다. . 또 다른 하나는 동일한 클래스에서 유형 검사 단계에서 나누기가 0으로 발생하는지 여부를 결정하는 것이 불가능하다는 것을 깨달았을 때입니다. 왜냐하면 런타임에 숫자가 0인지 확인하는 것도 마찬가지이기 때문입니다. 중단 문제의 버전.

---

나는 문자 그대로 같이 "호스트가 영구적으로 중지 여부를 확인하는 플러그인 모니터를 쓰기", 중단 문제가 할당되었다. 정말? 좋아요, 저는 임계 값을 줄 게요. "아니요, 나중에 다시 올 수 있으니까요."

많은 이론적 설명이 이어졌습니다.

---

몇 년 전, Basic Infinite Loop Finder 또는 BILF라는 제품에 대한 리뷰를 읽은 기억이납니다. BILF는 Microsoft Basic 소스 코드를 스캔하고 종료되지 않은 루프를 찾습니다. 코드에서 무한 루프를 찾을 수 있다고 주장했습니다.

리뷰어는 해당 프로그램이 모든 경우에 작동하려면 중지 문제를 해결해야하며 모든 경우에 작동하지 않는 이유에 대한 수학적 증거를 제공해야한다는 점을 지적했습니다.

다음 호에서는 회사 대표로부터 다음 릴리스에서 문제가 해결 될 것이라고 설명하는 편지를 게시했습니다.

업데이트 : 나는 imgur에서 기사의 이미지를 발견했습니다. 잘못된 잡지를 기억했습니다. 그것은 바이트가 아니라 크리에이티브 컴퓨팅이었습니다. 그렇지 않으면 내가 기억했던 것과 거의 같습니다.

imgur 에서 고해상도 버전을 볼 수 있습니다 .

---

제가 지금 작업하고있는 프로젝트 는 모든면에서 결정 불가능한 문제를 가지고 있습니다. 단위 테스트 생성기이므로 일반적으로 "이 프로그램이 수행하는 작업 " 이라는 질문에 답하는 것이 좋습니다. 중지 문제의 예입니다. 개발 중에 발생한 또 다른 문제는 "동일한 두 가지 (테스트) 기능이 제공됨"입니다 . 또는 "두 호출 (어설 션)의 순서가 중요 합니까? "

이 프로젝트의 흥미로운 점은 모든 상황 에서 이러한 질문에 답할 수는 없지만 90 %의 시간 동안 문제를 해결하는 현명한 솔루션을 찾을 수 있다는 것입니다.이 영역에서는 실제로 매우 좋습니다.

컴파일러 / 인터프리터 최적화, 정적 코드 분석 도구, 심지어 리팩토링 도구와 같이 다른 코드에 대해 추론하려는 다른 도구는 중단 문제를 해결할 수 있습니다 (따라서 해결 방법을 찾아야 함).

---

예 1. 내 보고서에 몇 페이지가 있습니까?

프로그래밍을 배울 때 데이터에서 예쁜 보고서를 인쇄하는 도구를 만들었습니다. 분명히 모든 보고서 생성기를 종료하는 것이 보고서 생성기가 될 수 있도록 매우 유연하고 강력하기를 원했습니다.

보고서 정의는 너무 유연해서 Turing이 완성되었습니다. 변수를보고, 대안을 선택하고, 루프를 사용하여 일을 반복 할 수 있습니다.

보고서 인스턴스의 페이지 수인 기본 제공 변수 N을 정의 했으므로 각 페이지에 "페이지 n / N"이라는 문자열을 넣을 수 있습니다. 두 번의 패스를 수행했습니다. 첫 번째 패스는 페이지 수를 세는 데 (N이 0으로 설정된 동안), 두 번째 패스는 첫 번째 패스에서 얻은 N을 사용하여 실제로 페이지를 생성했습니다.

때때로 첫 번째 패스는 N을 계산하고 두 번째 패스는 다른 수의 페이지를 생성합니다 (이제 0이 아닌 N은 보고서가 수행 한 작업을 변경하기 때문입니다). 나는 N이 안정 될 때까지 반복적으로 패스를 시도했습니다. 그런 다음 이것이 해결되지 않으면 어떨까요?

그러면 "반복이 보고서가 생성하는 페이지 수에 대해 안정된 값을 결정하지 않을 경우 최소한 사용자를 감지하고 경고 할 수 있습니까?"라는 질문으로 이어집니다. 다행히이 무렵에 저는 Turing, Godel, 계산 가능성 등에 대한 읽기에 관심이 있었고 연결을 만들었습니다.

몇 년 후 나는 MS Access가 때때로 "Page 6 of 5"를 인쇄하는 것을 발견했습니다. 이것은 정말 놀라운 일입니다.

예제 2 : C ++ 컴파일러

컴파일 프로세스에는 템플릿 확장이 포함됩니다. 템플릿 정의는 여러 전문화에서 선택할 수 있으며 ( "조건"으로 사용하기에 충분 함) 재귀적일 수도 있습니다. 그래서 그것은 템플릿 정의가 언어이고 유형이 값이며 컴파일러가 실제로 인터프리터 인 튜링 완전 (순수 기능) 메타 시스템입니다. 이것은 사고였습니다.

결과적으로 주어진 C ++ 프로그램을 검사하고 컴파일러가 원칙적으로 프로그램의 성공적인 컴파일로 종료 될 수 있는지 여부를 말할 수 없습니다.

컴파일러 공급 업체는 재귀 템플릿의 스택 깊이를 제한하여이 문제를 해결합니다. g ++에서 깊이를 조정할 수 있습니다.

---

여러 달 전에 저는 1500도 용광로 안팎으로 금속 부품 바구니를 옮기기 위해 매우 복잡한 철도 시스템을 구현하는 회사의 컨설턴트를 지원했습니다. 트랙 자체는 작업장에있는 상당히 복잡한 '미니 레일 야드'였으며 두 곳에서 교차했습니다. 여러 개의 전동 팔레트가 일정에 따라 부품 바구니를 이동합니다. 용광로 문을 가능한 한 짧게 여는 것이 매우 중요했습니다.

공장이 전체 생산 중이었기 때문에 컨설턴트는 자신의 스케줄링 알고리즘을 테스트하기 위해 '실시간'으로 소프트웨어를 실행할 수 없었습니다. 대신 그는 예쁘고 그래픽 같은 시뮬레이터를 작성했습니다. 가상 팔레트가 그의 화면상의 트랙 레이아웃에서 움직이는 것을 보면서 "일정 충돌이 있는지 어떻게 알 수 있습니까?"라고 물었습니다.

그의 빠른 대답은 "쉬움-시뮬레이션은 결코 멈추지 않을 것입니다."

---

정교한 정적 코드 분석은 중단 문제에 부딪 힐 수 있습니다.

예를 들어 Java 가상 머신이 코드 조각이 범위를 벗어난 배열 인덱스에 액세스하지 않는다는 것을 증명할 수있는 경우 해당 검사를 생략하고 더 빠르게 실행할 수 있습니다. 일부 코드의 경우 이것이 가능합니다. 더 복잡해지면 중단 문제가됩니다.

---

This is still a problem for shaders in GPU applications. If a shader has an infinite loop (or a very long calculation), should the driver (after some time limit) stop it, kill the fragment, or just let it run? For games and other commercial stuff, the former is probably what you want, but for scientific/GPU computing, the latter is what you want. Worse, some versions of windows assume that since the graphics driver has been unresponsive for some time, it kills it, which artificially limits the computing power when doing computation on the GPU.

There's no API for a application to control how the driver should behave or set the timeout or something, and there's certainly no way for the driver to tell if your shader is going to finish or not.

I don't know if this situation has improved recently, but I'd like to know.

---

Another common version of this is "we need to eliminate any deadlocks in our multi-threaded code". A perfectly-reasonable request, from the management perspective, but in order to prevent deadlocks in the general case, you have to analyse every possible locking state that the software can get into, which is, no surprise, equivalent to the halting problem.

There are ways to partially "solve" deadlocks in a complex system by imposing another layer on top of the locking (like a defined order of acquisition), but these methods are not always applicable.

---

Why this is equivalent to the halting problem:

Imagine you have two locks, A and B, and two threads, X and Y. If thread X has lock A, and wants lock B also, and thread Y has lock B and wants A too, then you have a deadlock.

If both X and Y have access to both A and B, then the only way to ensure that you never get into the bad state is to determine all of the possible paths that each thread can take through the code, and the order in which they can acquire and hold locks in all those cases. Then you determine whether the two threads can ever acquire more than one lock in a different order.

But, determining all of the possible paths that each thread can take through the code is (in the general case) equivalent to the halting problem.

---

Perl's testing system maintains a test counter. You either put the number of tests you're going to run at the top of the program, or you declare that you're not going to track it. This guard against your test exiting prematurely, but there are other guards so it's not all that important.

Every once in a while somebody tries to write a program to count the number of tests for you. This is, of course, defeated by a simple loop. They plow ahead anyway, doing more and more elaborate tricks to try and detect loops and guess how many iterations there will be and solve the halting problem. Usually they declare that it just has to be "good enough".

Here's a particularly elaborate example.

---

I was once working on an integration project in the ATM (Automated Teller Machines) domain. The client requested me to generate a report from my system for transactions sent by the country switch which were not received by my system!!

---

I found a Berkeley paper: Looper: Lightweight Detection of Infinite Loops at Runtime http://www.eecs.berkeley.edu/~jburnim/pubs/BurnimJalbertStergiouSen-ASE09.pdf

LOOPER may be useful since most infinite loops are trivial errors. However, this paper doesn't even mention the halting problem!

What do they say about their limitations?

[LOOPER] typically cannot reason about loops where non-termination depends on the particulars of heap mutation in every loop iteration. This is because our symbolic execution is conservative in concretizing pointers, and our symbolic reasoning insufficiently powerful. We believe combining our techniques with shape analysis and more powerful invariant generation and proving would be valuable future work.

In other words, "the problem will be fixed in the next release".

---

From the Functional Overview of (Eclipse) Visual Editor:

The Eclipse Visual Editor (VE) can be used to open any .java file. It then parses the Java source code looking for visual beans. ...

Some visual editing tools will only provide a visual model of code that that particular visual tool itself has generated. Subsequent direct editing of the source code can prevent the visual tool from parsing the code and building a model.

Eclipse VE, however, ... can either be used to edit GUIs from scratch, or from Java files that have been 'hardcoded' or built in a different visual tool. The source file can either be updated using the Graphical Viewer, JavaBeans Tree or Properties view or it can be edited directly by the Source Editor.

Maybe I should stick with Matisse for now.

관련이 없습니다 . Eclipse 내에서 중단 문제를 묻는 사람이 있습니다.

공정하게 말하면 VE의 도메인은 매우 제한적이며 아마도 반사와 같은 까다로운 일에 열광하지 않을 것입니다. 그럼에도 불구하고 모든 Java 파일에서 GUI를 구축한다는 주장은 멈춰있는 것처럼 보입니다.

---

"코드에 버그가 없는지 어떻게 확신 할 수 있습니까?"

참고 URL : https://stackoverflow.com/questions/235984/when-have-you-come-upon-the-halting-problem-in-the-field