현장에서 정지 문제가 발생한 때는 언제입니까?[닫은]

Question

당신은 언제 개인적으로 그런 일을 겪어본 적이 있습니까? 정지 문제 해당 영역에서?이는 동료/상사가 계산의 근본적인 한계를 위반하는 솔루션을 제안한 경우 또는 해결하려는 문제가 실제로 해결 불가능하다는 것을 스스로 깨달은 경우일 수 있습니다.

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

Answer 1

나 문자 그대로 "호스트가 영구적으로 다운되었는지 여부를 결정하기 위해 모니터 플러그인을 작성하십시오"에서와 같이 정지 문제를 할당했습니다. 진지하게? 좋아, 그래서 나는 단지 임계 값을 줄 것이다. "아니요, 나중에 다시 올 수 있기 때문에."

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

Answer 2

몇 년 전, 기본 무한 루프 파인더 또는 BILF라는 제품에 대한 리뷰 (Byte Magazine, I Believe)를 읽은 것을 기억합니다. BILF는 Microsoft 기본 소스 코드를 스캔하고 종료되지 않은 루프를 찾아야했습니다. 코드에서 무한 루프를 찾을 수 있다고 주장했습니다.

검토자는 모든 경우에 그 프로그램이 작동하기 위해서는 정지 문제를 해결해야 할 것이며 모든 경우에 작동 할 수없는 이유에 대한 수학적 증거를 제공하기까지 충분히 정통했습니다.

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

업데이트: 나는 Imgur에 관한 기사의 이미지를 가로 질러 달렸다. 나는 잘못된 잡지를 기억했다. 바이트가 아닌 창의적인 컴퓨팅이었습니다. 그렇지 않으면, 그것은 내가 기억했던 것과 거의 같습니다.

당신은 그것의 고해상도 버전을 볼 수 있습니다 Imgur.

Answer 3

내가 지금하고있는 프로젝트 그 모든 것에 대해 명확하지 않은 문제가 있습니다. 그것은 단위 테스트 생성기이므로 일반적으로 성취하려고하는 것은 질문에 답하는 것입니다. "이 프로그램이하는 일". 이는 중단 문제의 사례입니다. 개발 중에 발생한 또 다른 문제는입니다 "두 가지 (테스트) 기능이 동일하게 주어집니다."? 또는 "이 두 전화의 순서 (어설 션)가 중요합니까?"?

이 프로젝트의 흥미로운 점은 그 질문에 대답 할 수 없지만 모두 상황, 당신 ~할 수 있다 시간의 90%를 해결하는 스마트 솔루션을 찾으십시오.이 도메인의 경우 실제로는 매우 좋습니다.

컴파일러/통역자 최적화, 정적 코드 분석 도구, 심지어 리팩토링 도구와 같은 다른 코드에 대해 추론하려는 다른 도구는 정지 문제에 맞는 경우 (따라서 해결 방법을 찾도록 강요 될 것입니다).

Answer 4

예시 1.내 보고서는 몇 페이지인가요?

나는 프로그래밍을 배울 때 데이터로부터 예쁜 보고서를 인쇄하는 도구를 만들면서 놀았습니다.분명히 나는 ​​그것이 정말 유연하고 강력하기를 원했기 때문에 모든 보고서 생성기를 종료하는 보고서 생성기가 될 것입니다.

보고서 정의는 매우 유연하여 Turing Complete가 되었습니다.변수를 보고, 대안 중에서 선택하고, 루프를 사용하여 반복할 수 있습니다.

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

때로는 첫 번째 패스에서 N을 계산한 다음 두 번째 패스에서 다른 수의 페이지를 생성하기도 합니다(왜냐하면 이제 0이 아닌 N이 보고서의 내용을 변경하기 때문입니다).N이 안정될 때까지 반복적으로 패스를 시도했습니다.그러다가 이것이 절망적이라는 것을 깨달았습니다. 만약 그것이 안정되지 않으면 어떻게 될까요?

이것은 "반복이 보고서가 생성하는 페이지 수에 대한 안정적인 값으로 절대 안정되지 않을 경우 사용자를 최소한 감지하고 경고 할 수 있습니까?" 다행히도이 시점까지 나는 튜링, 고델, 계산 성 등에 대해 읽는 데 관심이있었습니다.그리고 연결을 했습니다.

몇 년 후 나는 MS Access가 가끔 "6/5페이지"를 인쇄한다는 것을 알게 되었는데, 이는 정말 놀라운 일이었습니다.

예 2:C++ 컴파일러

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

결과적으로 특정 C++ 프로그램을 검사하고 컴파일러가 원칙적으로 프로그램의 성공적인 컴파일로 종료될 수 있는지 여부를 말하는 것은 불가능합니다.

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

Answer 5

많은 달 전에 나는 매우 복잡한 철도 시스템을 구현하고있는 회사의 컨설턴트를 지원하고있었습니다. 트랙 자체는 상점 층에서 상당히 복잡한 '미니 라일러'로 몇 곳에서 교차했습니다. 몇몇 동력 팔레트는 일정에 따라 주변의 부품 바구니를 셔틀로 옮길 것입니다. 퍼니스 문이 가능한 한 짧은 시간 동안 열려있는 것이 매우 중요했습니다.

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

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

Answer 6

정교한 정적 코드 분석은 중단 문제가 발생할 수 있습니다.

예를 들어, Java 가상 머신이 코드 조각이 바운드 외부 인덱스에 액세스 할 수 없음을 증명할 수 있다면 해당 점검을 더 빨리 생략하고 실행할 수 있습니다. 일부 코드의 경우 이것이 가능합니다. 더 복잡 해짐에 따라 중단 문제가됩니다.

Answer 7

이는 여전히 GPU 애플리케이션의 셰이더에 대한 문제입니다.셰이더에 무한 루프(또는 매우 긴 계산)가 있는 경우 드라이버가(일정 시간 제한 후) 이를 중지하거나 조각을 종료해야 합니까, 아니면 그냥 실행되도록 놔두어야 합니까?게임 및 기타 상업용 항목의 경우 아마도 전자가 원하는 것일 수 있지만 과학/GPU 컴퓨팅의 경우 후자가 원하는 것입니다.더 나쁜 것은 일부 버전의 창에서는 그래픽 드라이버가 한동안 응답하지 않았기 때문에 그래픽 드라이버가 종료되어 GPU에서 계산을 수행할 때 컴퓨팅 성능이 인위적으로 제한된다고 가정합니다.

애플리케이션이 드라이버의 작동 방식이나 시간 초과 등을 설정하는 방법을 제어하는 ​​API가 없으며 드라이버가 셰이더가 완료될지 여부를 알 수 있는 방법도 없습니다.

최근에는 이런 상황이 좋아졌는지는 모르겠지만, 알고 싶습니다.

Answer 8

이것의 또 다른 일반적인 버전은 "우리는 멀티 스레드 코드의 교착 상태를 제거해야합니다"입니다. 관리 관점에서 완벽하게 합리적 인 요청이지만 일반적인 경우 교착 상태를 방지하려면 소프트웨어가 들어갈 수있는 모든 잠금 상태를 분석해야합니다.

정의 된 획득 순서와 같이 잠금 위에 다른 레이어를 부과하여 복잡한 시스템에서 교착 상태를 부분적으로 "해결"하는 방법이 있지만 이러한 방법이 항상 적용되는 것은 아닙니다.

---

이것이 정지 문제와 동등한 이유 :

두 개의 잠금 장치, A와 B와 X와 Y의 두 개의 스레드가 있다고 상상해보십시오. 스레드 X에 A가 잠금 A가 있고 잠금 B도 원한다면 스레드 Y에 B가 있고 A가 A를 원한다면 교착 상태가 있습니다.

x와 y가 모두 A와 B에 액세스 할 수 있다면, 나쁜 상태에 들어 가지 않는 유일한 방법은 각 스레드가 코드를 통해 취할 수있는 가능한 모든 경로와 그 순서를 결정하는 것입니다. 모든 경우에 자물쇠를 획득하고 잡을 수 있습니다. 그런 다음 두 스레드가 다른 순서로 둘 이상의 잠금을 얻을 수 있는지 여부를 결정합니다.

그러나 각 스레드가 코드를 통해 취할 수있는 가능한 모든 경로를 결정하는 것은 (일반적인 경우) 중단 문제와 동일합니다.

Answer 9

Perl의 테스트 시스템은 테스트 카운터를 유지합니다. 프로그램 상단에서 실행할 테스트 수를 넣거나 추적하지 않을 것이라고 선언합니다. 이것은 당신의 시험이 조기에 빠져 나가는 것에 대한 경비를 보호하지만, 다른 경비원이 있으므로 그다지 중요하지는 않습니다.

가끔씩 누군가가 당신을 위해 테스트 수를 세기 위해 프로그램을 작성하려고합니다. 물론 이것은 단순한 루프로 패배합니다. 그들은 어쨌든 앞으로 나아가면서 루프를 탐지하고 감지하고 반복이 얼마나 많은지 추측하고 정지 문제를 해결하기 위해 점점 더 정교한 트릭을 수행합니다. 보통 그들은 단지 그것이 "충분히 좋다"고 선언합니다.

다음은 특히 정교한 예입니다.

Answer 10

한 번 ATM (Automated Teller Machines) 도메인의 통합 프로젝트를 진행하고있었습니다. 고객은 내 시스템에서받지 못한 Country Switch에서 보낸 거래에 대한 내 시스템에서 보고서를 생성하도록 요청했습니다 !!

Answer 11

버클리 종이를 찾았습니다. 루퍼 : 런타임에 무한 루프의 경량 감지 http://www.eecs.berkeley.edu/~jburnim/pubs/burnimjalbertstergiousen-ase09.pdf

루퍼는 대부분의 무한 루프가 사소한 오류이므로 유용 할 수 있습니다. 그러나이 논문 정지 문제를 언급조차하지 않습니다!

그들은 그들의 한계에 대해 무엇을 말합니까?

루퍼]는 일반적으로 비 말단이 모든 루프 반복에서 힙 돌연변이의 세부 사항에 의존하는 루프에 대해 추론 할 수 없습니다. 이것은 우리의 상징적 처형이 포인터를 구체화하는 데 보수적이며, 우리의 상징적 추론은 불충분하게 강력하기 때문입니다. 우리는 우리의 기술을 모양 분석과 더 강력한 불변 생성 및 증명과 결합하는 것이 귀중한 미래의 작업 일 것이라고 생각합니다.

다시 말해, "문제는 다음 릴리스에서 수정 될 것"입니다.

Answer 12

로부터 (Eclipse) 비주얼 편집기의 기능 개요:

Eclipse Visual Editor (VE)는 열 수 있습니다. 어느 .java 파일. 그런 다음 비주얼 콩을 찾는 Java 소스 코드를 구문 분석합니다. ...

일부 시각적 편집 도구는 특정 시각적 도구 자체가 생성 한 시각적 코드 모델 만 제공합니다. 소스 코드를 후속 직접 편집하면 시각적 도구가 코드를 구문 분석하고 모델을 구축하는 것을 방지 할 수 있습니다.

그러나 Eclipse Ve는 ... GUI를 처음부터 편집하는 데 사용하거나 '하드 코딩'되거나 다른 시각적 도구로 내장 된 Java 파일에서 사용될 수 있습니다. 소스 파일은 그래픽 뷰어, javabeans 트리 또는 속성보기를 사용하여 업데이트 될 수 있습니다. 직접 편집 할 수 있습니다 소스 편집기에 의해.

아마도 지금은 Matisse를 고수해야 할 것입니다.

관련이 없습니다. 여기 누군가가 있습니다 요청 일식 내의 중단 문제.

공정하게 말하면, VE의 도메인은 상당히 제한되어 있으며, 반사와 같은 까다로운 것들에 대해서는 미치지 않을 것입니다. 그럼에도 불구하고 GUI를 구축하겠다는 주장 어느 Java 파일은 정지 해 보입니다.

Answer 13

"코드가 100% 버그가 없음을 어떻게 확신 할 수 있습니까?"