유효법
Effective method논리학, 수학, 컴퓨터학, 특히 금속공학 및 계산가능성 이론에서 효과적인 방법이나[1] 효과적인 절차는 특정 계층의 직관적인 '효과적인' 수단에 의해 문제를 해결하는 절차다.[2] 효과적인 방법은 때로는 기계적인 방법이나 절차라고도 불린다.[3]
정의
효과적인 방법의 정의는 방법 자체보다 더 많은 것을 포함한다. 어떤 방법이 효과적이라고 불리기 위해서는, 그것은 문제의 종류에 관해서 고려되어야 한다. 이 때문에 한 가지 방법은 한 계층의 문제에 대해 효과적일 수 있고 다른 계층에 대해서는 효과적이지 않을 수 있다.
방법은 다음과 같은 기준을 충족할 때 공식적으로 문제 종류에 대해 효과적이라고 불린다.
- 그것은 한정된 수의 정확하고 유한한 지시로 구성된다.
- 해당 등급의 문제에 적용되는 경우:
- 그것은 항상 한정된 수의 스텝 후에 마무리된다.
- 그것은 항상 정답을 만들어 낸다.
- 원칙적으로 글쓰기 외에는 아무런 도움 없이 사람이 할 수 있다.
- 그것의 지침은 성공하기 위해서는 엄격하게 지켜져야만 한다. 다시 말해, 성공하기 위해서는 창의력이 필요하지 않다.[4]
선택적으로, 그 방법이 클래스 밖에서 발생하는 문제에 적용될 때, 그 방법이 답인 것처럼 결과를 결코 반환하지 않도록 요구될 수도 있다. 이 요건을 추가하면 효과적인 방법이 있는 클래스의 집합을 줄일 수 있다.
알고리즘
함수의 값을 계산하는 효과적인 방법은 알고리즘이다. 효과적인 방법이 존재하는 함수를 때때로 효과적으로 계산할 수 있다고 한다.
계산 가능한 함수
효과적인 계산가능성에 대한 공식적인 특성화를 제공하기 위한 몇 가지 독립적인 노력이 제안된 다양한 정의(일반 재귀 함수, 튜링 머신, λ-미적분)로 이어졌고, 이는 나중에 동등한 것으로 나타났다. 이러한 정의에 의해 포착된 개념은 재귀적이거나 효과적인 계산가능성으로 알려져 있다.
Church-Turing 논문은 두 개념은 일치한다고 말한다: 효과적으로 계산할 수 있는 숫자-이론적 함수는 재귀적으로 계산할 수 있다. 이것은 수학적 진술이 아니기 때문에 수학적 증거로는 증명할 수 없다.
참고 항목
참조
- ^ 헌터, 제프리, 메탈로직: 캘리포니아 대학 출판부의 표준 제1차 주문 논리 메타테리오리 소개, 1971
- ^ Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms".
{{cite journal}}: Cite 저널은 필요로 한다.journal=(도움말) - ^ Copeland, B.J.; Copeland, Jack; Proudfoot, Diane (June 2000). "The Turing-Church Thesis". AlanTuring.net. Turing Archive for the History of Computing. Retrieved 23 March 2013.
- ^ 케임브리지 철학사전, 효과적인 절차
- S. C. 클레네(1967), 수학 논리학. 다시 인쇄된 도버, 2002년 ISBN 0-486-42533-9, 페이지 233 ff, esp. 231.
