본문바로가기
함께 풀고 싶은 문제
직접 문제를 올려 폴리매스 출제자에 이름을 올리세요!
문제를 잘 표현할 수 있는 제목을 짓고, 문제에 사용된 수학 분야를 말머리로 달아주세요.
[세상을 바꿀 문제] [논리학,전산학] 예측불가한 임의의 숫자를 만들 수 없음을 증명 등 난수에 대한 4가지 문제
돼지파이 2021.02.21 19:50

세상을 바꿀 문제는 아니지만 함께 풀고 싶어서 올립니다. 여기에는 여러가지 문제가 있는데 한 문제라도 해결되거나 해결된 사례를 알려주시면 좋을것 같습니다.

저도 대략 추측은 하는데 정리를 해본적은 없어서 수학적으로 전문적으로 나타내실 수 있는 분들의 도움을 받고 싶은 부분이 있습니다.

 

우리는 흔히 random이라는 '임의의 수'를 나타내고는 합니다. 그런데 전산쪽에서 프로그래밍을 하다보면 이 임의의 수를 생성하는게 불가능하다는 것을 깨닫게 됩니다. 폰 노이만은 이에대해 "랜덤을 이야기하는 자는 누구든 어딘가 죄를 짓고 있는것이다-유사 난수만 생성할 수 있으므로-"라고 표현했다고 합니다.

왜냐하면 컴퓨터(튜링 머신)로 무언가 생성한다는 것은 이미 프로그램된 규칙을 갖고 있다는 것을 의미해서, 동일한 프로그램이 동일한 초기 조건으로 시작되면 그 수는 이미 임의의 수가 아니거든요.

 

따라서 대략 임의의 수처럼 보이는 흐름을 만드는 다양한 방법이 있는데 대략 이렇습니다

(대개 필연적으로 난수는 지속되는 숫자의 흐름, 즉 stream을 만드는 문제로 귀결됩니다. 연속적으로 어떤 임의의 수를 생산하는 것이지요)

 

1) 무리수를 하나 만든 후 임의의 자리수에서 계속 아래 자리를 생산해냅니다. 대략 pi값으로 해도 좋습니다.

   대략 머리속에 10진수의 값이 연속하는 것들이 떠오르실텐데, 한자리 한자리 뿜어내면 됩니다.

   pi를 예로 들면 3.14 아래 자리 수부터 시작하면 1, 5, 9, ... 이렇게 난수가 생기겠지요. 신기한 것은 이렇게 생성된 0~9까지의 숫자가 동일한 빈도수로 나타날까요? 대답은 '그렇다' 입니다. 이건 또 임의의 수 주제와는 별도로 재미있는 주제입니다. 대개 사람들에게 이 사실을 물어보면 본능적으로 '그렇다'라고 대답합니다. 왜냐하면 편중될 이유가 없다고 생각하지요.

  무리수는 어떤 진법으로 나타내든 특정 숫자에 편중되지 않습니다.

 <-- 증명할 수 있을까요? 아래 2)에 힌트가 있습니다.

 

2) 난수 문제에서 재미있는 것은 이 난수를 2진수로 생성해내면, 0과 1이 같은 비율이지만 순서는 예측할 수 없는 bit의 흐름으로 나타내는 것이 가장 원초적입니다. 이래야만 사실은 어떤 진수로 만들어도 특정 숫자에 편중되지 않습니다. 즉, 어떤 진법으로 나타낼 수 없다는 사실 자체가 2진수에서 0과 1이 같은 비율이며 예측할 수 없다는 조건이 될 수 있다고 생각합니다. 그러면 예측할 수 없는 임의의 난수라는 표현은 다시 한번 말씀드리면 0과 1이 불규칙하게 뿜어져 나오는데, 결과적으로 0과 1의 비율은 비슷해야 합니다.

 이게 좀 신기하죠. 불규칙해야하는데 0이 너무 많이 나왔다면 곧이어 1이 더 많이 나와야하는 상황이 됩니다. 좀 난감하죠

<-- 난수를 몇가지 등급으로 나눠서 제대로 정의할 수 있을까요? 0과 1이 좀 균등하지 않더라도 어떤 의미에서는 분포가 다른 난수라고 주장할 수도 있다는 생각이 들더라고요.

 

3) 4)는 자연스럽게 3)은 앞의 컴퓨터로 만드는 프로그램이 임의의 난수를 생성할 수 없다는 증명이고 4)는 난수를 생성하는(예측할 수 없다는) 방법을 제시하는 일입니다.

 

관련하여 공부하신 분들의 참고 자료나 증명, 더 깊은 내용들에 대해 코멘트를 부탁드립니다.

개인적으로는 양자역학이나 엔트로피를 공부하다가 갑자기 난수 문제에 관심을 가지게 되었고요.

 

이 문제 어떠셨나요?

유익해요

2

웃겨요

0

신기해요

0

어려워요

0

  •  
    S.K.H Lv.5 2021.02.21 22:30

    흠...생각하고 있는데 잘....

    댓글 작성하기 좋아요0 댓글수1
    •  
      숫자파이 Lv.5 2021.02.22 16:45 비밀댓글
      비밀 댓글이 등록 되었습니다!
  •  
    원형파이 Lv.9 2021.02.22 23:47

    난수를 사전에 쳐보면 아래와 같은 뜻이 나옵니다.

    '특정한 배열순서나 규칙적 의미를 갖지 않는 연속적인 임의의 수.'

    즉, 아무런 규칙 없이 무작위, 순수한 무작위를 의미합니다.

    2번에서 0이 많이 나왔다면 1이 더 많이 나와야 한다고 하셨는데요.

    이는 보장할 수 없습니다.

    물론, 무작위이므로 많은 실험을 할 수록 결과는 균등하게 분포될 것입니다.

    이는 확률적인 기본적인 특징이긴 하나, 실험의 횟수가 몇 번 이상이 되어야 이가 성립할 지는 모릅니다.

    영원히 그 값이 1 차이가 나면서 균등하지 않을 수도 있죠.

    확률적인 이해에 대하여 실험 횟수를 따지지 않고 0과 1의 개수가 비슷해야 한다는 것은 대다수의 경우 맞아 떨어지겠지만, 틀릴 경우도 빈번히 생길겁니다.

    또 다른 얘기로 넘어가서, 균등하다 라는 기준을 완벽하게 세우는 것은 미터를 정의하는 것과는 조금 다릅니다.

    각 수마다 정확히 같은 횟수씩 나오면 균등한걸까요?

    꼭 그런게 아니라면, 균등하다 라는 정의를 문제에서 제시하셨던 '등급' 을 통하여 구별할 수 있지 않을까 싶습니다.

    예를 들어, 각 수마다 나온 횟수를 기록한 후 max-min의 값과 총 횟수의 합에 대한 비율, 혹은 그 외의 기준을 삼아 수치로 구별할 수 있을 겁니다.

    이렇게 생각을 해도, 이 '수치'를 어떻게 잡고, 이 '등급'을 어떻게 나누냐.. 라는 또 다른 난관에 부딪히게 됩니다.

    난수, 무작위에 대한 기준을 단 하나의 수치로 결정하는 것은 굉장히 애매합니다.

    확률적으로 난수에는 균등한 분포가 이루어져야 맞지만, 현실에서는 그렇지만은 않다는거죠.

    3번에 대한 제 의견은 이렇습니다.

    컴퓨터를 이용하여 난수를 발생시킨다고 가정을 해보겠습니다.

    컴퓨터는 인간과 다릅니다.

    결국 어느 데이터에서 무작위처럼 보이는 수 데이터를 뽑아와야 할테고요.

    이 데이터는 인간의 작품인 컴퓨터의 데이터답게 인간이 만들어놓은 자료입니다.

    실제로 C++의 rand 함수를 이용하여 무작위의 수를 발생시켜보면, '주기'가 생성되는 것을 볼 수 있습니다.

    아하, 그럼 인간이 머릿속으로 난수를 생각핼 수만 있다면 인간의 데이터를 활용하여 무작위 난수를 발생시킬 수 있지 않을까요?

    제 생각은 그렇지 않습니다.

    인간 또한 태어나서부터, 혹은 그 이전부터 수많은 일들을 겪고, 수많은 수치에 접합니다.

    수를 모르는 갓난아기가 1~9중 무작위로 수를 하나 고르라고 지시받았을 때 1을 고르는 것과 같은 기적이 일어나지만은 않는다면, 결론적으로 우리가 만들어내는 난수 또한 경험을 기반하여 만들어집니다.

    경험은 또한 반복적이고, 주기적이며 순수한 무작위라고 보기 정말 어려운 부분입니다.

    언젠가 보았고, 언젠가 보았다는 것을 기억하는 수치 중에서 무작위로 고른다고는 하지만, 결국 인간은 인간이다보니 완벽한 무작위를 만들어내기는 힘듭니다.

    그리도 완벽한 인간에게 '무작위'라는 능력은 주어지지 않았나봅니다.

    4번에 대해서는 이런 생각을 해보았습니다.

    위에서 제가 말씀드렸다시피 인간은 완벽한 무작위를 만들어내기 어려운 종족입니다.

    물론 인간의 자료를 기반으로 한 인간의 작품들도 마찬가지입니다.

    그러니까... 자연에서 얻을 수 있다면... 어떨까 라는 생각이 들었습니다.

    꽃잎의 수를 따져본다고 하자면 잘 알려져 있듯 피보나치 수열이라는 '규칙'에 대체로 기반하죠.

    자연에서 또한 생존하거나 생존하기 유리한 꼴을 갖기 위하여 수학에 기반합니다.

    수학에 인간이 모르는 또다른 원리가 있고 자연에서 이를 이용하고 있다면 이를 이용하여 무작위 난수를 고려해볼 수도 있습니다.

    정작 난수를 원하는것은 인간이다보니 이는 모순이 되죠.

     

    여기까지가 제 의견입니다.

    잘 도움이 되실지는 모르겠지만 고민해보기 좋은 문제 인것 같습니다.

    유익한 문제 출제해주셔서 감사드립니다.

    댓글 작성하기 좋아요1 댓글수3
    •  
      S.K.H Lv.5 2021.02.23 12:41

      저는 작은 확률도 실현 될 수 있다와 같이 생각해서 풀고 있습니다.이 문제를 정확히 풀려면 주사의를 수천번쯤 돌려야 할지도 모르겠네요...

      좋아요0
    •  
      숫자파이 Lv.5 2021.02.23 20:05

      @S.K.H

      주사의→주사위

      좋아요1
    •  
      돼지파이 Lv.2 2021.02.26 20:30

      생각 공유 감사드립니다 : )

      이 문제를 잘 정립해두면 자연 법칙이 과연 튜링 머신처럼 작동하는가 등등도 응용할 수 있다고 생각합니다.

       

      좋아요0
  •  
    △π Lv.9 2021.02.25 09:15
    확인요청중

    특정한 값을 가지지 않는 이상, 하나의 숫자에 편중될 경우의 수가 굉장히 적기 때문이라고 생각합니다.

    양자역학이나 엔트로피를 공부하시다가 난수 문제에 관심을 두신 것처럼, 저 또한 이 문제를 엔트로피의 개념으로 보고 있습니다.

    공기의 구성 성분이 하나 하나 다 독립적으로 떨어져서 제각기 다른 움직임을 보이는 것 보다는 현재처럼 모두 한데 섞여 다니는 경우의 수가 훨씬 많죠

    따라서 엔트로피가 낮습니다.

    난수도 마찬가지라고 생각합니다.

    어느 한 수에 지나치게 편중되는 경우의 수가 모두 고루 분포되는 경우의 수보다 현저하게 낮기 때문이라고 생각합니다.

     

    특히 0과 1은 차이가 훨씬 분명하게 납니다.

    어느 한 책에서 읽은 바가 있는데, 정확히 기억은 나지 않습니다.

    동전던지기를 했을 때, 만약 1/10만큼만 평균치에서 벗어나도 그 확률은 2%가 채 되지 않습니다.

    0과 1이 나올 확률이 동일할 때, 결국 높은 확률로 0과 1의 비율은 비슷해지죠.

     

    난수의 등급을 나눠서 정의한다고 제안해주셨는데 저는 잘 모르겠습니다.

    어떤 난수던지 확률적인 방법으로 똑같은 시행을 걸쳐서 생성된 것인데, 010111101010001010101010101011101101과 111111111111111111111111111111111111을 등급이 다른 난수라고 생각해야 할 지 잘 모르겠습니다. 물론 후자는 생성될 확률이 1/2^36이긴 하지만요.

     

    컴퓨터로 만드는 프로그램은, 실제 의미에서의 "난수"를 생성할 수 없습니다. 수를 공정하게 분배하기 위한 그저 확률적인 방법에 불과하죠. 

    당장 인터넷에 "컴퓨터 난수"라고 쳐보면, 여러가지의 난수 생성법이 존재합니다.

    하지만 이 방법이 존재한다는 것 부터 난수는 실패한 것입니다.

    진정한 의미에서의 "완전한 무작위의 난수"가 나오지 않으니까요.

    난수의 의의는, 각 숫자가 나올 가능성이 모두 동일하다는 것으로 알고 있습니다.

    따라서 무작위의 난수는 나올 수 없다고 생각합니다.

     

    그래서 진정한 의미의 난수가 아니라면 어떻게 해야 할까요?

    저는 이렇게 생각합니다.

    아무런 의미가 없는 숫자를 복잡하면서 짧은 시간의 단위로 계속 읊는 것이죠.

    그러다가 사용자가 출력을 하게 되면, 그 순간의 숫자를 출력하는 것입니다.

    이렇게 하면, 진정한 난수로서의 개념은 사라지지만, 그 결과를 예측할 수 없을 것입니다.

     

    제 개인적인 의견일 뿐입니다

    참고해주시면 정말 감사드립니다!

     

    +원주율 파이는 모든 수가 고르게 나오는 '정규수'인지는 증명되지 않았습니다!

    댓글 작성하기 좋아요0 댓글수6
    •  
      원형파이 Lv.9 2021.02.25 23:58

      :god:

      좋아요0
    •  
      숫자파이 Lv.5 2021.02.26 11:12

      비댓으로 변경해주세요!!!

      좋아요0
    •  
      △π Lv.9 2021.02.26 12:28

      @숫자파이

      일부로 공댓으로 한 겁니다. 생각을 공유할 수 있도록 말이죠

      좋아요0
    •  
      숫자파이 Lv.5 2021.02.26 12:30

      그래도 확인요청까지 했으면...

      좋아요0
    •  
      숫자파이 Lv.5 2021.02.26 12:30

      좋아요0
    •  
      돼지파이 Lv.2 2021.02.26 20:31

      생각 공유 감사드려요.

      그리고 파이의 각 숫자들이 나오는 빈도수를 구하는 python code를 실험해보았는데요,

      증명할 수 없지만 자리수가 늘어갈수록 각 자리수의 숫자 빈도는 거의 같습니다. 신기하죠.

      저는 그것보다 이 질문을 학생들에게 던졌을때 본능적으로 거의 비슷한 빈도를 보일거라고 대답하는게 더 신기하답니다.

      어떻게 그것을 본능적으로 다들 알고 있을까요? : )

       

      좋아요0
  • 폴리매스 문제는 2019년도 정부의 재원으로 한국과학창의재단의 지원을 받아 수행된 성과물입니다.

  • ☎문의 02-6749-3911