태그 보관물: lambda-calculus

lambda-calculus

람다 미적분학에서 함수가 익명 인 것이 중요한 이유는 무엇입니까? 콤비 네이터의

Jim Weirich의 ‘ 기능 프로그래밍모험 ‘이라는 강의를보고있었습니다 . 이 강의에서 그는 Y- 콤비 네이터의 개념을 소개합니다.이 조합은 본질적으로 고차 함수의 고정 점을 찾습니다.

그가 언급 한 동기 중 하나는 람다 미적분학을 사용하여 재귀 함수를 표현할 수 있어야 교회의 이론 (실제로 계산 가능한 모든 것이 람다 미적분학을 사용하여 계산할 수 있음)이 유지되도록하는 것입니다.

람다 미적분은 명명 된 함수, 즉

n(x,y)=x+y

이름 ‘ ‘을 가질 수 없으면 익명으로 정의해야합니다.

n

(x,y)x+y

람다 미적분학이 명명되지 않은 함수를 갖는 것이 왜 중요한가? 명명 된 기능이있는 경우 어떤 원칙을 위반합니까? 아니면 내가 짐의 비디오를 오해 한 것입니까?



답변

이 문제에 관한 주요 정리는 16 세기 말 영국의 수학자 윌리엄 셰익스피어 ( William Shakespeare )에 기인한다 . 이 주제에 대한 그의 가장 잘 알려진 논문 은 1597 년에 ” 로미오와 줄리엣 ” 이라는 제목 으로 출판되었지만 연구 작업은 몇 년 전에 수행되었지만 Arthur Brooke과 William Painter와 같은 선구자에게 영감을주었습니다.

그의 주요 결과는 Act II에 명시되어 있습니다. 장면 II유명한 정리입니다 .

이름이 뭐야? 우리가 장미라고 부르는 것은
다른 이름으로도 달콤한 냄새가납니다.

이 정리는 “이름이 의미에 기여하지 않는다”는 것으로 직관적으로 이해 될 수 있습니다.

이 논문의 대부분은 정리를 보완하고 이름이 의미를 부여하지 않더라도 끝없는 문제의 원인이라는 것을 보여주는 예에 전념하고 있습니다.

셰익스피어가 지적한 바와 같이, 이름은 의미를 바꾸지 않고 변경 될 수 있으며, 나중에 Alonzo Church 와 그의 추종자들에 의해 변환

α

이라고 불렀 습니다. 결과적으로 이름으로 표시되는 것을 결정하는 것이 반드시 간단한 것은 아닙니다. 이로 인해 이름 의미 연결이 지정된 환경 개념 개발 및 이름과 관련된 의미를 결정할 때 현재 환경을 파악하는 규칙과 같은 다양한 문제가 발생합니다. 이로 인해 컴퓨터 과학자들은 당황 스러워서 악명 높은 Funarg 문제 와 같은 기술적 어려움을 겪었습니다.. 환경은 일부 인기있는 프로그래밍 언어에서 여전히 문제로 남아 있지만 일반적으로 셰익스피어가 그의 논문에서 작성한 예제만큼이나 치명적 일수록 물리적으로 더 안전하지 않은 것으로 간주됩니다.

이 문제는 주변에서 제기 된 문제도 공식 언어 알파벳과 공식적인 시스템이되어야 할 이론, 동형 사상 최대 정의 그래서 것을 밑줄에 관해서는, 알파벳의 상징이 추상적 인 실체는 , 그들이 어떻게 “구체화”등의 독립 일부 세트의 요소.

셰익스피어의이 주요 결과는 또한 과학이 마법이나 종교와 분리되어 존재 나 의미가 진정한 이름을 가질 수 있음을 보여준다.

이 모든 것의 결론은 이론적 작업의 경우 실제 작업과 일상 생활에서 더 단순하게 느껴지더라도 이름으로 방해받지 않는 것이 더 편리하다는 것입니다. 그러나 엄마라고하는 모든 사람이 당신의 어머니 인 것은 아닙니다.

참고 :
이 문제는 최근 20 세기 미국의 논리 학자 Gertrude Stein 에 의해 해결되었습니다
. 그러나 그녀의 수학자 동료들은 여전히 ​​그녀의 주요 정리 의 정확한 기술적 의미를 숙고하고 있습니다 .

장미는 장미입니다 장미는 장미입니다.

“Sacred Emily”라는 짧은 커뮤니케이션으로 1913 년에 출판되었습니다.


답변

λ

λ

π

ν엑스.

π

λ

λ

λ

이자형에프=미디엄나는

(λ에프.)미디엄

λ


답변

아이디어는 이름이 필요하지 않다고 생각합니다. 이름이 필요한 것으로 보이는 것은 익명 함수로 작성할 수 있습니다.

람다 미적분학을 어셈블리 언어와 같이 생각할 수 있습니다. 어셈블리 강의에서 누군가 어셈블리 언어에는 객체 지향 상속 트리가 없다고 말할 수 있습니다. 그런 다음 상속 트리를 구현하는 영리한 방법을 생각할 수 있지만 그게 요점이 아닙니다. 요점은 물리적 컴퓨터를 프로그래밍하는 가장 기본적인 수준에서 상속 트리가 필요하지 않다는 것입니다.

람다 미적분학에서 요점은 이름이 가장 기본적인 수준에서 알고리즘을 설명하는 데 필요하지 않다는 것입니다.


답변

나는 지금까지 3 가지 답변, 특히 @babou의 셰익스피어 분석을 즐기고 있지만 질문의 본질이라고 생각하는 것에 대해서는 밝히지 않습니다.

λ- 미적분은 함수에 함수를 적용 할 때마다 이름을 함수에 바인딩합니다. 문제는 이름의 부족이 아닙니다.

“문제는 이름을 참조하여 함수가 간단하게 호출 할 수 없다는 것입니다.”

(순수한 Lisp에서 이름-> 함수 바인딩은 함수 본문 내에 있지 않습니다. 이름으로 함수를 호출하려면 함수가 함수를 참조하는 환경을 참조해야합니다. Pure Lisp에는 없습니다. 주기적 데이터 구조 : Impure Lisp는 함수가 참조하는 환경을 변경하여이를 수행합니다.)

@MartinBerger가 지적했듯이 λ-calculus가 이름으로 함수 호출을하지 않는 역사적 이유는 λ-calculus 를 연역 논리를 포함한 수학의 기초로 사용하려고 할 때 Curry의 역설 을 배제하려는 시도였습니다 . Y 결합기와 같은 기술은 자체 참조 없이도 재귀를 허용하므로 작동하지 않았습니다.

Wikipedia에서 :

함수 r = (λ.x x x ⇒ y)를 정의 할 수 있다면 r r = (r r ⇒ y).

경우에는 r r사실 다음 y사실이다. 경우 r r거짓 다음 r r ⇒ y모순되는 사실이다. 그래서 y사실과 같은 y명령문이 될 수있는 문은 사실 입증 할 수있다.

r r종료하지 않는 계산입니다. 논리 r r는 존재하지 않는 값에 대한 표현식 으로 간주됩니다 .


답변