- 다양한 주제에 대해 자유롭게 글을 작성하는 게시판입니다.
Date 17/02/10 22:45:46
Name   April_fool
Link #1   http://scienceon.hani.co.kr/34696
Link #2   https://namu.wiki/w/%EC%A0%95%EC%A7%80%20%EB%AC%B8%EC%A0%9C
Subject   로또 번호 생성 프로그램과 정지 문제

어제 올린 로또 번호 생성 프로그램을 보다, 문득 소개하고 싶은 것이 생겨 글을 씁니다.

예를 들어 말입니다, 제가 올린 로또 번호 생성 프로그램이 실제로 몇 번만에 로또 번호를 맞출 수 있는지 한번 검증해보고 싶어졌다고 해 봅시다. 그래서 저는 다음과 같은 프로그램을 작성하였습니다.

  1. import random
  2.  
  3. def plusAll(a):
  4.     result = 0
  5.     for i in a:
  6.         result += i
  7.     return result
  8.  
  9. def lottoNumGen():
  10.     while True:
  11.         a = random.sample(range(1, 45+1), 6)
  12.         if 135 <= plusAll(a) <= 141:
  13.             result = sorted(a)
  14.             return result
  15.  
  16. count = 0
  17. = random.sample(range(1, 45+1), 6)
  18. = sorted(a)
  19.  
  20. while True:
  21.     b = lottoNumGen()
  22.     b = sorted(b)
  23.     count += 1
  24.     if a == b:
  25.         print(a, count)
  26.         break

파이썬 언어를 모르시는 분들을 위해 위의 프로그램을 간략하게 설명하면 다음과 같습니다.

  1. 1에서 45 사이의 랜덤한 번호 6개로 이루어진 수열 [a]를 만듭니다. 수열을 오름차순으로 정렬하여 순서를 맞춥니다. 수열의 각 숫자는 서로 겹치지 않습니다.
  2. 수열 a와 모든 조건이 똑같지만, 각 숫자를 모두 합치면 135에서 141 사이에 있다는 조건을 추가한 수열 [b]를 만듭니다.
  3. 수열 a와 b가 서로 일치하는지 비교합니다.
  4. 수열 a와 b가 일치하지 않으면, 일치할 때까지 수열 b를 새로 만들어서 다시 비교합니다.
  5. 수열 a와 b가 일치하면, 일치한 수열과 지금까지 수열 b를 몇 번 만들었는지 횟수를 출력하고 프로그램을 종료합니다.

여기서 문제입니다. 과연 이 프로그램은 정상적으로 종료될까요?

이런 식으로, 컴퓨터 프로그램이 언젠가 정상적으로 종료되는가 아니면 종료되지 않고 무한루프에 빠져 영원히 실행되는가를 판정하는 것을 정지 문제(halting problem)이라고 부릅니다. 조금 더 엄밀하게 말하자면, 정지 문제의 내용은 다음과 같습니다.

“임의의 프로그램 A가 주어졌을 때, A가 정상적으로 종료하는지 무한히 계속하는지를 결정하라.”

(출처 : http://scienceon.hani.co.kr/34696)

그럼, 과연 위에서 제가 작성한 프로그램을 실행시키면 언젠가는(비록 오랜 시간이 걸릴지라도) 결과값이 나올까요? 답은 [알 수 없다]입니다. 왜일까요? 제가 위에서 작성한 프로그램에는 이것과 관련된 아주 심각한 문제점이 하나 숨어 있습니다. 그것이 무엇인지는 한번 직접 생각해보시기 바랍니다. 아마도 프로그래밍을 배우신 분이시라면 보자마자 바로 알아챌 수 있으실 겁니다.

1936년에 ‘컴퓨터의 아버지’ 앨런 튜링은 위에서 언급한 정지 문제를 풀 수 있는 일반적인 방법(알고리즘)은 존재하지 않는다는 것을 증명하였습니다. 이게 무슨 소리냐 하면, 아무 프로그램이나 집어넣어서 이 프로그램이 정상적으로 종료된다고 보장할 수 있는 방법은 없다는 것입니다. 앨런 튜링의 증명 방법을 단순하게 설명하면 다음과 같습니다.

  1. 정지 문제를 풀 수 있다고 가정한다. (귀류법)
  2. 정지 문제를 풀 수 있는 절차(알고리즘)를 이용하여 프로그램 A를 만든다. 프로그램 A는 다음과 같은 프로그램이다.
    1. 프로그램 A는 다른 프로그램 B를 입력받는다.
    2. 만약 프로그램 B가 정상적으로 종료되는 프로그램이 맞으면, 프로그램 A는 무한루프에 빠져 응답을 멈춘다.
    3. 만약 프로그램 B가 무한루프에 빠져 응답을 멈추면, 프로그램 A는 정상적으로 종료된다.
  3. 프로그램 A에 자기 자신(프로그램 A)을 입력한다.
  4. 프로그램 A는 자기 자신이 정상적으로 종료된다고 해도, 무한루프에 빠진다고 해도 모순에 빠진다. 따라서 정지 문제는 판정할 수 없다(undecidable).

이 증명의 의미를 확장하면, [어떤 임의의 프로그램이 완전무결한지를 보증할 수 있는 방법은 없다]는 것이 됩니다. 다시 말해서, 어떤 프로그램에 버그가 전혀 없음을 증명할 수는 없다는 것이지요. 버그가 있다는 것은 보여주면 그만이지만, 버그가 전혀 없다는 것은 증명할 수가 없는 것입니다.

그럼, 컴퓨터가 자동으로 프로그램의 버그를 찾아내거나 하는 것은 완전히 불가능한 것일까요? 그렇지는 않습니다. 위에서 인용한 곳에는 이런 문장이 있군요. 제가 설명하는 것보다 이 문장을 인용하는 것이 더 적당할 것 같군요.

“종료 문제를 연구하는 소프트웨어공학자들은 가능한 모든 프로그램이 아닌 우리에게 가치가 있는 프로그램으로 문제의 범위를 제한한 뒤에 종료 문제에 대한 부분적인 해답을 얻는 것을 목표로 합니다. 임의의 모든 프로그램에 대해 종료 문제를 해결하는 것은 불가능하지만, 그럼에도 불구하고 상당수의 프로그램에 대해서는 해결이 가능하다는 뜻입니다 (마찬가지로, 완벽한 백신은 이론적으로 불가능하지만 매우 믿을 만한 백신은 충분히 가능하다는 희소식이기도 합니다). 이들이 연구하는 기술을 자동종료 증명(Automated Termination Proof)이라고 합니다. 주어진 소프트웨어가 언제나 정상적으로 종료하는지를 자동으로 증명하는 도구를 만드는 것입니다.”

그럼 여기서, 제가 위에서 작성한 프로그램이 어째서 결과값이 나올지 안 나올지를 알 수 없는지 혹시 눈치채지 못하신 분들을 위해 이유를 공개하겠습니다.

만약 수열 a의 값이 수열 b처럼 총합의 범위가 135에서 141 사이에 있으면 확률에 의해 언젠가는 결과값이 나올 수 있을 것입니다. 그런데 수열 a의 총합의 범위가 135에서 141 사이를 벗어나 있으면, 아무리 수열 b를 생성해도 수열 a와 b가 일치하는 일은 일어날 수가 없습니다. 수열 b는 총합의 범위가 135에서 141 사이라는 제약조건이 있으니까요. 문제는 수열 a가 어떤 값으로 생성될지는 완전히 랜덤이라는 점입니다. 따라서 위 프로그램을 실행시켜보기 전에는 위 프로그램이 정상적으로 종료될지 아니면 무한루프에 빠질지 알 수가 없지요.

이상, 오늘의 뻘글이었습니다.

p.s.
이 글의 내용이 재미있으셨다면, 다음 글도 한번 읽어보세요.
http://www.joysf.com/4602163




1


    목록
    번호 제목 이름 날짜 조회 추천
    공지 티타임 게시판 이용 규정 2 Toby 15/06/19 30474 6
    14564 사회UN 세계행복보고서 2024가 말하는, 한국과 동북아에 대한 의외의 이야기 13 카르스 24/03/26 1079 7
    14563 음악[팝송] 맥스 새 앨범 "LOVE IN STEREO" 2 김치찌개 24/03/26 159 1
    14560 일상/생각2년차 사원입니다 9 공대왜간공대 24/03/25 1010 10
    14559 음악[팝송] 피더 엘리아스 새 앨범 "Youth & Family" 김치찌개 24/03/24 111 0
    14558 오프모임이승탈출 넘버원 3회차 12 치킨마요 24/03/24 665 0
    14557 일상/생각인지행동치료와 느린 자살 7 골든햄스 24/03/24 980 8
    14556 요리/음식까눌레 만드는 이야기 10 나루 24/03/23 464 5
    14555 오프모임[아주급한벙]신촌 홍곱창or정통집 오늘 19:00 34 24/03/23 922 2
    14554 일상/생각아들이 안경을 부러뜨렸다. 8 whenyouinRome... 24/03/23 694 26
    14553 정치지금 판세가 어떨까요 를 가늠할수 있는 지표 32 매뉴물있뉴 24/03/22 1907 0
    14552 음악[팝송] 저스틴 팀버레이크 새 앨범 "Everything I Thought It Was" 김치찌개 24/03/22 150 1
    14551 스포츠태국 전 관람 후 집빈남 24/03/21 484 0
    14550 일상/생각와이프랑 덕담 중입니다. 3 큐리스 24/03/21 669 4
    14549 게임최근 해본 스팀 게임들 플레이 후기 13 손금불산입 24/03/21 487 5
    14548 음악[팝송] 리암 갤러거,존 스콰이어 새 앨범 "Liam Gallagher & John Squire" 6 김치찌개 24/03/20 187 1
    14547 꿀팁/강좌그거 조금 해주는거 어렵나? 8 바이엘(바이엘) 24/03/20 1113 13
    14546 스포츠[MLB] 블레이크 스넬 샌프란시스코와 2년 62M 계약 김치찌개 24/03/20 201 0
    14544 의료/건강불면증 개선에 도움되는 멜라토닌 효능 11 후랑키 24/03/19 832 1
    14542 역사연개소문 최후의 전쟁, 최대의 승첩: 9. 나가며 2 meson 24/03/17 226 3
    14541 역사연개소문 최후의 전쟁, 최대의 승첩: 8. 태산봉선(泰山封禪) meson 24/03/16 214 1
    14540 음악[팝송] 아리아나 그란데 새 앨범 "eternal sunshine" 2 김치찌개 24/03/16 239 1
    14539 일상/생각22살. 정신병 수급자 고졸. 9 경주촌박이 24/03/15 1179 1
    14538 역사연개소문 최후의 전쟁, 최대의 승첩: 7. 선택과 집중 1 meson 24/03/15 185 3
    14537 일상/생각건망증,그리고 와이프 1 큐리스 24/03/15 568 1
    목록

    + : 최근 2시간내에 달린 댓글
    + : 최근 4시간내에 달린 댓글

    댓글