위키원
"오라클 머신"의 두 판 사이의 차이
leejia1222 (토론 | 기여) (새 문서: '''오라클 머신'''(oracle machine)은 판정문제를 연구하는 데 사용되는 추상기계이다. 한글로는 '''신탁 기계'''라고 한다. 일반적으로 오라클...) |
leejia1222 (토론 | 기여) |
||
| 1번째 줄: | 1번째 줄: | ||
'''오라클 머신'''(oracle machine)은 판정문제를 연구하는 데 사용되는 추상기계이다. 한글로는 '''신탁 기계'''라고 한다. | '''오라클 머신'''(oracle machine)은 판정문제를 연구하는 데 사용되는 추상기계이다. 한글로는 '''신탁 기계'''라고 한다. | ||
| − | 일반적으로 오라클 머신은 | + | 일반적으로 오라클 머신은 튜링머신(turing machine)에 오라클이라는 블랙박스를 붙여놓은 것이라고 할 수 있다. 이때 오라클, 즉 신탁은 어떤 판정 문제를 단 한 번의 동작으로 풀 수 있는 장치이다.<ref name="위키">〈[https://ko.wikipedia.org/wiki/%EC%8B%A0%ED%83%81_%EA%B8%B0%EA%B3%84 신탁 기계]〉, 《위키백과》</ref> 신탁이 풀 수 있는 문제는 모든 복잡도 조율에 해당하기 때문에 심지어는 정지문제와 같이 컴퓨터로 풀 수 없는 문제까지도 풀 수 있다. |
오라클 머신은 추상화된 블랙박스를 통해 단일연산으로 특정한 결정문제를 풀 수 있는 기계를 의미한다. 이를 풀어서 해석해보면, 오라클 머신은 계산이론에서 1) 예/아니오로 대답할 수 있는 결정 문제를 연구하는 데 사용되는 2) 추상기계이다. 스무고개를 상상해보자. 스무고개에서 풀 수 있는 모든 문제는 예/아니오의 결정문제로 환원될 수 있다. 추상기계라는 말은 실제로 있는 장치가 아닌, 단지 상상속의 기계라는 의미이다. 어떤 종류의 문제를 질문하면 바로 예/아니오로 답을 주는 이상적인, 그러나 이론적 증명에만 사용하는 수학적인 [[컴퓨터]] 모델로, 현재 컴퓨터라는 장치가 수학적으로 가능하다는 것을 보여준 튜링머신이 바로 추상기계다.<ref>박충식, 〈[http://www.econovill.com/news/articleView.html?idxno=346578 (박충식의 인공지능으로 보는 세상) 오라클 머신 또는 신탁 기계]〉, 《이코노빌》, 2018-09-25</ref> | 오라클 머신은 추상화된 블랙박스를 통해 단일연산으로 특정한 결정문제를 풀 수 있는 기계를 의미한다. 이를 풀어서 해석해보면, 오라클 머신은 계산이론에서 1) 예/아니오로 대답할 수 있는 결정 문제를 연구하는 데 사용되는 2) 추상기계이다. 스무고개를 상상해보자. 스무고개에서 풀 수 있는 모든 문제는 예/아니오의 결정문제로 환원될 수 있다. 추상기계라는 말은 실제로 있는 장치가 아닌, 단지 상상속의 기계라는 의미이다. 어떤 종류의 문제를 질문하면 바로 예/아니오로 답을 주는 이상적인, 그러나 이론적 증명에만 사용하는 수학적인 [[컴퓨터]] 모델로, 현재 컴퓨터라는 장치가 수학적으로 가능하다는 것을 보여준 튜링머신이 바로 추상기계다.<ref>박충식, 〈[http://www.econovill.com/news/articleView.html?idxno=346578 (박충식의 인공지능으로 보는 세상) 오라클 머신 또는 신탁 기계]〉, 《이코노빌》, 2018-09-25</ref> | ||
| − | + | 튜링머신은 테이프에 입력값을 작성하여 신탁값에 전달한다. 신탁은 단 한 번의 계산을 마치고 테이프에 작성되어 있는 입력값을 지우고 결과값을 쓴다. 때로는 튜링머신이 오라클 머신의 입력과 출력 용도로 두 개의 테이프를 가진다고 가정하기도 하며, 오라클 머신은 한 번의 동작으로 어떤 결정문제를 풀 수 있는 블랙박스를 가진 튜링머신으로 상상한다.<ref>Faustinus, 〈[http://blog.naver.com/777gud/110081719818 신탁]〉, 《네이버 블로그》, 2010-03-01</ref> 이러한 상상들을 통해 컴퓨터에 주어지는 문제를 연구한다. | |
| − | 정치문제와 같이 컴퓨터로 풀 수 없는 문제가 있다. 이에도 풀 수 있는 신탁이 존재한다고 가정할 수 있는데, 이러한 문제를 해결할 수 있는 신탁이 달린 기계는 초월기계라고 부른다. 정지 문제의 역설이 이 초월기게에 그대로 적용된다. 즉, 특정한 | + | 정치문제와 같이 컴퓨터로 풀 수 없는 문제가 있다. 이에도 풀 수 있는 신탁이 존재한다고 가정할 수 있는데, 이러한 문제를 해결할 수 있는 신탁이 달린 기계는 초월기계라고 부른다. 정지 문제의 역설이 이 초월기게에 그대로 적용된다. 즉, 특정한 튜링머신이 특정한 입력에 대해 멈출지의 여부를 판별할 수 있지만, 동일한 정지신탁이 달린 기계가 멈출지의 여부는 판별할 수 없다는 것이다. 이런 사실에서 기계에 대한 위계를 생각할 수 있으며, 이것을 산술 위계라고 한다.<ref name="위키"></ref> |
{{각주}} | {{각주}} | ||
2019년 6월 13일 (목) 11:04 판
오라클 머신(oracle machine)은 판정문제를 연구하는 데 사용되는 추상기계이다. 한글로는 신탁 기계라고 한다.
일반적으로 오라클 머신은 튜링머신(turing machine)에 오라클이라는 블랙박스를 붙여놓은 것이라고 할 수 있다. 이때 오라클, 즉 신탁은 어떤 판정 문제를 단 한 번의 동작으로 풀 수 있는 장치이다.[1] 신탁이 풀 수 있는 문제는 모든 복잡도 조율에 해당하기 때문에 심지어는 정지문제와 같이 컴퓨터로 풀 수 없는 문제까지도 풀 수 있다.
오라클 머신은 추상화된 블랙박스를 통해 단일연산으로 특정한 결정문제를 풀 수 있는 기계를 의미한다. 이를 풀어서 해석해보면, 오라클 머신은 계산이론에서 1) 예/아니오로 대답할 수 있는 결정 문제를 연구하는 데 사용되는 2) 추상기계이다. 스무고개를 상상해보자. 스무고개에서 풀 수 있는 모든 문제는 예/아니오의 결정문제로 환원될 수 있다. 추상기계라는 말은 실제로 있는 장치가 아닌, 단지 상상속의 기계라는 의미이다. 어떤 종류의 문제를 질문하면 바로 예/아니오로 답을 주는 이상적인, 그러나 이론적 증명에만 사용하는 수학적인 컴퓨터 모델로, 현재 컴퓨터라는 장치가 수학적으로 가능하다는 것을 보여준 튜링머신이 바로 추상기계다.[2]
튜링머신은 테이프에 입력값을 작성하여 신탁값에 전달한다. 신탁은 단 한 번의 계산을 마치고 테이프에 작성되어 있는 입력값을 지우고 결과값을 쓴다. 때로는 튜링머신이 오라클 머신의 입력과 출력 용도로 두 개의 테이프를 가진다고 가정하기도 하며, 오라클 머신은 한 번의 동작으로 어떤 결정문제를 풀 수 있는 블랙박스를 가진 튜링머신으로 상상한다.[3] 이러한 상상들을 통해 컴퓨터에 주어지는 문제를 연구한다.
정치문제와 같이 컴퓨터로 풀 수 없는 문제가 있다. 이에도 풀 수 있는 신탁이 존재한다고 가정할 수 있는데, 이러한 문제를 해결할 수 있는 신탁이 달린 기계는 초월기계라고 부른다. 정지 문제의 역설이 이 초월기게에 그대로 적용된다. 즉, 특정한 튜링머신이 특정한 입력에 대해 멈출지의 여부를 판별할 수 있지만, 동일한 정지신탁이 달린 기계가 멈출지의 여부는 판별할 수 없다는 것이다. 이런 사실에서 기계에 대한 위계를 생각할 수 있으며, 이것을 산술 위계라고 한다.[1]
각주
참고자료
- 〈신탁 기계〉, 《위키백과》
- 박충식, 〈(박충식의 인공지능으로 보는 세상) 오라클 머신 또는 신탁 기계〉, 《이코노빌》, 2018-09-25
