검색 결과
둘러보기로 이동
검색으로 이동
문서 제목 일치
- [[계산 가능성 이론]]에서 '''재귀 집합'''({{llang|en|recursive set}}) 또는 '''계산 가능 집합'''({{llang|en|computable s 조건을 일반화하여 [[재귀 열거 집합]]의 정의를 얻을 수 있다. ...2 KB (127 단어) - 2022년 7월 28일 (목) 00:34
- '''재귀 언어'''({{llang|en|recursive language}}) 또는 '''귀납 언어'''는 [[형식 언어]]의 [[재귀 집합|재귀적]]인 부분집합이다. '''결정 가능 언어'''(decidable language)라고도 한다. 모든 재귀 언어의 모임은 [[복잡도 종류]] '''[[R (복잡도)|R]]''' 클래스와 같다. [[촘스키 위계]]에는 별도로 분류되어 있지 않다 ...2 KB (54 단어) - 2022년 2월 6일 (일) 07:02
- {{소문자|title=μ-재귀 함수}} ...또는 간단히 '''재귀 함수'''란, [[자연수]]에서 자연수로의 '계산가능한' [[부분 함수]]이다. [[재귀 이론]]에서는, μ-재귀 함수와 [[튜링 기계]]로 계산가능한 함수가 일치하는 것임이 알려져 있다. 유명한 예로 [[피보나치 수]] 등이 있다. ...6 KB (307 단어) - 2024년 5월 7일 (화) 04:05
- ...이다. 원시 재귀 함수의 클래스는 [[μ-재귀 함수]]의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 [[PR (복잡도)|PR]]로 표기되며, 이는 [[R (복잡도)|R]]의 일부이다. 원시 재귀 함수는 우선 자연수에서 자연수로의 함수, 즉 수론적 함수여야 한다. n개의 변수를 받는 이 함수를 n항 함수라 한다. ...2 KB (142 단어) - 2022년 2월 6일 (일) 07:02
- ...로, 문자열의 집합의 [[재귀 열거 집합|재귀 열거인 부분집합]]이다. [[촘스키 위계]]의 '''type-0 언어'''이기도 하다. 재귀 열거 언어의 모임을 '''[[RE (복잡도)|RE]]'''라고 한다. 재귀 열거 언어의 개념에 관한 세개의 동등한 주요 정리가 존재한다. ...3 KB (60 단어) - 2023년 3월 11일 (토) 14:02
- 자연수로 구성된 한 집합 S에 대하여, 정의역이 정확히 S인 [[μ-재귀 함수|부분 재귀 함수]] f가 존재할 때 S를 재귀적으로 열거가능하다고 한다. 이는 f가 정의된다는 것과 f의 입력이 S의 원소라는 것이 동치임을 의미 :* 집합 S는 재귀적으로 열거가능하다. 즉, S는 부분 재귀 함수의 정의역이다. ...5 KB (136 단어) - 2022년 7월 28일 (목) 00:27
- 레빈슨 [[재귀함수|재귀]] [[알고리즘]](Levinson recursion, 또는 Levinson-Durbin recursion)은 [[선형 대수학]]에서 ...1 KB (79 단어) - 2022년 2월 28일 (월) 16:05
문서 내용 일치
- '''재귀 언어'''({{llang|en|recursive language}}) 또는 '''귀납 언어'''는 [[형식 언어]]의 [[재귀 집합|재귀적]]인 부분집합이다. '''결정 가능 언어'''(decidable language)라고도 한다. 모든 재귀 언어의 모임은 [[복잡도 종류]] '''[[R (복잡도)|R]]''' 클래스와 같다. [[촘스키 위계]]에는 별도로 분류되어 있지 않다 ...2 KB (54 단어) - 2022년 2월 6일 (일) 07:02
- ...이다. 원시 재귀 함수의 클래스는 [[μ-재귀 함수]]의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 [[PR (복잡도)|PR]]로 표기되며, 이는 [[R (복잡도)|R]]의 일부이다. 원시 재귀 함수는 우선 자연수에서 자연수로의 함수, 즉 수론적 함수여야 한다. n개의 변수를 받는 이 함수를 n항 함수라 한다. ...2 KB (142 단어) - 2022년 2월 6일 (일) 07:02
- ...로, 문자열의 집합의 [[재귀 열거 집합|재귀 열거인 부분집합]]이다. [[촘스키 위계]]의 '''type-0 언어'''이기도 하다. 재귀 열거 언어의 모임을 '''[[RE (복잡도)|RE]]'''라고 한다. 재귀 열거 언어의 개념에 관한 세개의 동등한 주요 정리가 존재한다. ...3 KB (60 단어) - 2023년 3월 11일 (토) 14:02
- [[계산 가능성 이론]]에서 '''재귀 집합'''({{llang|en|recursive set}}) 또는 '''계산 가능 집합'''({{llang|en|computable s 조건을 일반화하여 [[재귀 열거 집합]]의 정의를 얻을 수 있다. ...2 KB (127 단어) - 2022년 7월 28일 (목) 00:34
- 자연수로 구성된 한 집합 S에 대하여, 정의역이 정확히 S인 [[μ-재귀 함수|부분 재귀 함수]] f가 존재할 때 S를 재귀적으로 열거가능하다고 한다. 이는 f가 정의된다는 것과 f의 입력이 S의 원소라는 것이 동치임을 의미 :* 집합 S는 재귀적으로 열거가능하다. 즉, S는 부분 재귀 함수의 정의역이다. ...5 KB (136 단어) - 2022년 7월 28일 (목) 00:27
- {{소문자|title=μ-재귀 함수}} ...또는 간단히 '''재귀 함수'''란, [[자연수]]에서 자연수로의 '계산가능한' [[부분 함수]]이다. [[재귀 이론]]에서는, μ-재귀 함수와 [[튜링 기계]]로 계산가능한 함수가 일치하는 것임이 알려져 있다. 유명한 예로 [[피보나치 수]] 등이 있다. ...6 KB (307 단어) - 2024년 5월 7일 (화) 04:05
- 느린 정렬은 [[재귀 (컴퓨터 과학)|재귀 알고리즘]]이다. * 처음의 절반을 재귀 정렬한다. (1.1) ...3 KB (180 단어) - 2024년 2월 24일 (토) 07:05
- * [[연립 일차 방정식]] <math>Mx=a</math>의 해: <math>O(n^2)</math> ([[레빈슨 재귀 알고리즘]]) * [[행렬식]] <math>\det M</math>: <math>O(n^2)</math> ([[레빈슨 재귀 알고리즘]]) ...2 KB (120 단어) - 2025년 3월 3일 (월) 12:11
- * [[μ-재귀 함수]] {{본문|재귀 집합}} ...2 KB (34 단어) - 2024년 6월 2일 (일) 23:01
- ...me{Open}(X))</math>의 [[부분 집합]] <math>S\subseteq X</math>가 다음 조건을 만족시키면, '''재귀 집합'''({{llang|en|recurrent set}})이라고 한다. 정의에 따라, 모든 [[Gδ 집합|G<sub>δ</sub> 집합]]은 자명하게 포화 집합이다. 모든 재귀 집합은 자명하게 [[조밀 집합]]이다. ...5 KB (282 단어) - 2024년 5월 21일 (화) 11:35
- ...ster Method'''(마스터 방법, 만능 방법), '''{{lang|en|Master Theorem}}'''(마스터 정리)는 [[재귀 관계식]]으로 표현한 [[알고리즘]]의 동작 시간을 [[점근 표기법|점근적]]으로 계산하여 간단하게 계산하는 방법이다. ...roduction to Algorithms]]''의 4.3절과 4.4절, '''4.5절'''에 설명되어 유명해졌으나, 이 방법이 모든 재귀 관계식을 풀 수 있는 건 아니다. ...2 KB (161 단어) - 2022년 2월 6일 (일) 07:01
- 레빈슨 [[재귀함수|재귀]] [[알고리즘]](Levinson recursion, 또는 Levinson-Durbin recursion)은 [[선형 대수학]]에서 ...1 KB (79 단어) - 2022년 2월 28일 (월) 16:05
- ...도출되는 성질을 구문론적 완전성(syntactical completeness)이라 한다. [[불완전성 정리]]는 어떠한 형식 체계가 재귀(recursion)의 개념을 나타낼 수 있을 정도로 강력하다면, [[무모순성]]과 구문론적 완전성을 동시에 가질 수 없음을 의미한다. ...1 KB (36 단어) - 2022년 2월 25일 (금) 15:38
- '''수단 함수'''(Sudan function)는 [[계산 이론]]에서 [[재귀]]적이지만 [[원시 재귀 함수|원시 재귀]]적이지는 않은 [[함수]]의 예이다. 이는 더 잘 알려진 [[아커만 함수]]의 경우에도 마찬가지이다. 1926년에 [[다비트 힐베르트]]는 모든 계산 가능한 함수가 원시 재귀 함수라고 추측했다. 이는 그의 제자인 [[가브리엘 수단]]과 [[빌헬름 아커만]]에 의해 빠르게 연속해서 출판된 다양한 기능을 사용하여 ...13 KB (1,567 단어) - 2024년 8월 7일 (수) 04:43
- [[함수]]의 [[재귀|재귀적]] [[정의 (논리학)|정의]]는 어떤 원소에 대한 함수의 결과를 다시 원소로 삼는 함수로 정의한다. 예를 들어 [[계승]] 함 ...는 모든 자연수 {{수학 변수|n}}에 대해 타당하다. 위 식에서 어떠한 {{수학 변수|n}}도 풀어쓰면 결국 0!=1이라는 '''[[재귀|재귀의 기초]]'''로 도달하기 때문이다. 이 정의는 거꾸로 올라가서 함수의 값을 계산하는 것으로도 생각할 수도 있다. 즉, {{수학| ...11 KB (383 단어) - 2024년 5월 18일 (토) 10:16
- ...터 시작하여 0 ~ 3 타입으로 분류된다. 이는 [[노엄 촘스키]]가 1956년 생성 문법을 체계적으로 정의하면서 구성한 것인데, [[재귀 문법]]을 규정하고 있지 않다. ...2 KB (85 단어) - 2024년 5월 3일 (금) 13:29
- 이 된다.(이는 재귀 관계를 조금만 생각해보면 명백하다. 파스칼 삼각형과 유사한 도식을 그리고, 맨 왼쪽 변과 그 바로 오른쪽 줄을 고려하면 된다) 따라서, ...3 KB (148 단어) - 2023년 1월 30일 (월) 08:26
- ...가장 먼저 발견된 것이기도 하다. 모든 원시 재귀 함수는 완전히 정의되고 계산 가능하지만 아커만 함수는 모든 전역적 재귀 함수가 원시 재귀 함수일 필요는 없다는 것을 보였다.<ref>{{인용|title=Understanding Formal Methods|first1=Jean ...udan)과 [[빌헬름 아커만]](Wilhelm Ackermann)은 계산의 기초를 연구하고 있었다. 수단과 아커만은 둘 다 [[원시 재귀 함수]]가 아닌 [[완전히 정의된 함수|완전히 정의된]] [[계산 가능 함수]] (어떤 문헌에서는 단순히 "재귀적"으로 표현한다)를 발 ...23 KB (1,673 단어) - 2025년 3월 13일 (목) 18:21
- ...다(즉, '무모순적'이다). 오늘날 "서수 ε<sub>0</sub>까지의 양화사-자유 [[초한귀납법]]의 추가 원리를 가진 원시적 [[재귀]] [[산술]]"이라고 불리는 이 다른 체계는 [[페아노 공리계]]보다 약하지도 강하지도 않다. 겐첸은 페아노 산술에 포함된 의심스러운 ...초한귀납법의 추가 원리를 가진 원시적 재귀 산술의 기초 이론 위에서 1차 페아노 공리의 일관성을 증명할 수 있음을 보여주었다. 원시적 재귀 산술은 훨씬 단순화된 형태의 산술로서 다소 논쟁적이지 않다. 추가 원리는 비형식적으로 유한한 뿌리가 있는 나무의 집합에 [[정렬 원순서 ...9 KB (117 단어) - 2024년 2월 18일 (일) 17:42
- 보편 계산 가능 함수의 정의역은 [[재귀 열거 집합|계산 열거 가능 집합]]이지만, [[계산 가능 집합]]은 아니다. 보편 계산 가능 함수의 정의역을 결정하는 문제는 [[정지 * Ω보다 작은 [[유리수]]의 집합은 [[재귀 열거 집합|계산 열거 가능 집합]]이다.{{sfn|Downey & Hirschfeld|loc=Theorem 5.1.11}} 이런 성질을 ...9 KB (311 단어) - 2025년 3월 13일 (목) 21:44