의미 상 의미 매핑이 가능한가?

이 질문에 대한 나의 열등한 표현에 사과드립니다. 나는 적절하게 질문 할 어휘가 있는지 확신하지 못합니다.의미 상 의미 매핑이 가능한가?

내가

⟦let x = x in x⟧ = ⊥

에 (최근에) 가깝다 뭔가를 쓴 적이 있지만 정말 내가 여기에 까다로운 무엇인가를 이해하는 데 실패하고있다. 나는 이것이 비생산적인 무한 루프라는 것을 알고 있기 때문에 진실로 ⊥이라고 주장 할 수있다. 또한, 나는

⟦let ones = 1:ones in ones⟧ = μ(λx.(1,x)) = (1, (1, (1, ...)))

과 같은 것을 주장 할 수 있지만, 그 elipsis는 무엇이 될까요? 아마도 AFA를 올바르게 사용한다면 완벽하게 잘 정의 된 수학적 객체 인 "1-and-tuples"의 무한한 수를 추정 할 수 있습니다. 그러나 어떻게하면 "1-and-tuples"의 유한 수가 아니라는 것을 당신에게 확신시킬 수 있습니까? 그런 다음 비생산적인 ⊥?

분명히이 문제는 정지 문제에 대한 답변이므로 일반적으로 할 수 없습니다.

그렇다면 의미 매핑을 마치 총체적인 함수 인 것처럼 어떻게 계산할 수 있습니까? 튜링 불완전 언어에 대한 의미론은 필연적으로 비 결정적입니까? 의미론은 항상 언어에 대한 대략적이고 비공식적 인 설명 일 뿐이라는 것을 의미하지만이 "구멍"은 더 나아질까요?

출처

2013-02-05 J. Abrahamson

약간의 코멘트 : (필립 JF의 아주 좋은 대답에 확장) coinductive 구조를 통해 방지 기술에 대한 자세한 내용은 –

잠시 전에 트위터 인수 중에 생성 한이 프로그램에 관심이있을 수 있습니다 : https : //gist.github.com/luqui/1379703 - 그것을 나타내는 지 알 수없는 하스켈 값 – luqui

@luqui 매우 근사하다! –

튜링 언어에 대한 이론적 모델은 없습니다. 당신의 언어가 강하게 정상화되면, 그것을 "해석하는"총체적인 기능을 빠져 나옵니다. 비 튜링 완전한 언어로 이론적 의미를 설정했거나 설정하지 않았을 수 있습니다. 그럼에도 불구하고 완전한 튜링과 완전한 튜링이 아닌 언어는 총 의미 론적 매핑 기능을 가진 이론적 의미론이 아닌 집합을 가질 수 있습니다.

여기에 문제가 있다고 생각하지 않습니다.

귀납적 및 공동 귀속 정의에는 차이가 있습니다. 우리는 이론적으로이 세트를 탐색 할 수 있습니다 :

이

정수의 목록의 유도 정의 읽기 :

설정된 [Z]가 작은 설정입니다 S 빈리스트가 S가되도록, 등을위한 그 임의의 ls은 S이고 n은 Z이고, (n,ls)은 S입니다.

이

도 [Z](0) = {[]}으로 "단계 색인"방법으로 제시 될 수 있습니다 [Z](n) = {(n,ls) | n \in Z, ls \in [Z](n-1)} 당신은 [Z] = \Union_{i \in N}([Z](n)을 정의 (당신은 자연수 믿는 경우!) 반면에

"목록"하스켈 더 자세히 coinductively

세트 [Z] (coinductive) 정의 된 "coinductive 스트림"과 관련되어 큰 세트이다 S 예를FORALL 그에서 S, x = [] 또는 x = (n,ls)에서 n에서 Z 및 ls에서 S.

즉, 동시성 정의는 거꾸로됩니다. 귀납적 정의가 일부 요소를 포함하는 가장 작은 집합을 정의하지만, 공동 정의는 모든 요소가 특정 양식을 취하는 가장 큰 집합을 정의합니다.

일부 유도 목록은 길이가 제한되어 있지만 일부 유도 목록은 무한히 길다는 것을 쉽게 보여줍니다. 당신의 본보기는 공동 도입이 필요합니다.

일반적으로 유도 성 정의는 "펑터의 최소 고정 점"이지만 유도 성 정의는 "펑터의 가장 큰 고정 점"이라고 생각할 수 있습니다. 가장 큰 고정 점이 그것의 "최종적인 coalgebra"인 동안 "초기 대수학"인 functor의 "최소 고정 점". 이를 의미 도구로 사용하면 집합 범주 이외의 범주에 속하는 항목을 쉽게 정의 할 수 있습니다.

나는 그것의 기능 공간이 CBN과 언어가 총 없기 때문에 하스켈은 이러한 펑

data ListGenerator a r = Cons a r | Nil 

instance Functor (ListGenerator a) where 
    fmap f (Cons a x) = Cons a (f x) 
    fmap _ Nil  = Nil

하스켈이 펑터를 설명하기위한 좋은 언어를 제공하지만

을 설명하는 좋은 언어를 제공하는 것을 발견, 우리는 어떤이 없습니다 우리는 가장 큰 fixpoint

data GF f = GF (f (GF f))

또는 실존

을 정량화 비 재귀의 정의를 어떻게해야합니까 있지만, 우리가 :(싶습니다 적어도 수정 포인트의 종류를 정의하는 방법

data GF f = forall r. GF r (r -> (f r))

가 보편적으로

data LF f = LF (forall r. (f r -> r) -> r)

편집을 정량화 우리는 엄격한 또는 전체 언어로 작업한다면, 최소한 fixpoint가 될 것이다 "작은"는 설정 이론적 개념이기 때문에 비록 "적어도"/ " 가장 큰 "구별은 옳지 않을 수도 있습니다. LF의 정의는 기본적으로 GF과 동형이며 "최소 고정 점"의 범주 형식주의 인 "자유 초기 대수"입니다. 나는 그것이 ⊥ 다음 비생산적인 어떤 유한 "한 -와 - 튜플"의 수와이 아니다 당신을 설득 할 수있는 방법

에 관한

?

내가이 게시물의 구성을 믿지 않는 한 당신은 할 수 없습니다. 내가 그렇게한다면, 당신의 정의는 나를 붙들어 버린다!. "ones은 (1,ones) 쌍으로 구성된 유도 성 흐름"이라면 나는 믿어야합니다! 나는 ones가 정의에 의하여 _|_이 아니므로, 유도에 의해 어떤 값이라도 n에 내가 n 것을 가지고 있고 그 다음에 그럴 수 없다는 것을 보여줄 수있다. 나는 당신의 주장을 부인하기 위해서만 시도 할 수 있습니다. http://www.cs.ox.ac.uk/people/daniel.james/unique/unique-tech.pdf

출처

2013-02-06 00:09:31

나는 haskell에서 가장 크고 가장 작은 고정 소수점이 일치한다고 생각 했습니까? – sclv

@sclv 어떤 특정 문맥에서 그 진술이 무엇을 의미하는지 모르겠습니다. functor의 초기 대수학은 최종 coalgebra와 확실히 일치합니다. 표준 구조는 비용 모델이 다릅니다. –

아, 내가 혼란스러워하는 이유를 알 수 있습니다. 일단 당신이'_ | _'에 대해 생각하기 시작하면, 일단 설정 이론적 의미론으로 빠져 나갈 수는 없습니다 --- 평범해야만합니다,하지만 거기에 우리가갑니다. non-recursive'LF'와'GF' 정의에 대해서도 감사드립니다! 대칭은 저를 위해 많은 것을 연결하고 있습니다. –

, 당신은 HINZE 제임스 ' "올바른 증명 고유 고정 소수점 원리"좀 걸릴 수 있습니다. .. 두 번째 예제에서 $ \ mu $ 대신 $ \ nu $가되어서는 안됩니다. (당신은 가장 큰 고정 점을 얻고 있습니다, 이것은 하스켈에서 일어나고있는 것입니다.)

출처

2013-02-06 04:44:56 sclv

답변

관련 문제