• Non ci sono risultati.

MR2895545 Review of Intrigila, Benedetto; Statman, Richard Solution to the range problem for combinatory logic. Fund. Inform. 111 (2011), no. 2, 203–222

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "MR2895545 Review of Intrigila, Benedetto; Statman, Richard Solution to the range problem for combinatory logic. Fund. Inform. 111 (2011), no. 2, 203–222"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

Previous Up Next

Citations From References: 1 From Reviews: 0 MR2895545 03B40

Intrigila, Benedetto(I-ROME2); Statman, Richard (1-CMU)

Solution to the range problem for combinatory logic. (English summary) Fund. Inform.111(2011),no. 2,203–222.

In lambda-calculus, the theoryH is obtained from β-conversion by identifying all closed unsolvable terms (or, equivalently, terms without head normal form). The range problem for H asks whether a closed term has always (up to equality in H) either an infinite range or a singleton range (that is, it is a constant function).

The paper tackles a modification of the above problem in the combinatory logic setting. A natural notion of head-normal form is defined for combinatory logic, albeit it lacks the equivalence between “terms without head normal form” and “terms being unsolvable”. LetHCLdenote the theory obtained from the weak-reduction by identifying all terms without head normal forms (of combinatory logic). The theoryHCLis weaker than H. The main result states that for every term M of combinatory logic, the set {M P |P closed} is either a singleton or infinite moduloHCL-equality.

Although this result adds evidence to the conjecture that the range problem forH has a positive answer, a negative answer to it was announced in September 2010 by

Polonsky. Luca Paolini

c

Riferimenti

Scarica adesso ( PDF - 1 pagine - 112.75 KB )

Documenti correlati

Studio ambientale sul fiume Noce: quadro conoscitivo ambientale e identificazione di interventi volti alla realizzazione di un parco fluviale del fiume Noce in Val di Sole: relazione tecnica

Lo stesso tratto presenta inoltre condizioni mediamente favorevoli alla navigazione tramite rafting nei mesi tardo-primaverili ed estivi (da maggio a luglio), quasi

Temporal correlation of population composition and environmental variables in the marine invader Ciona robusta

Physico‐chemical parameters (tem‐ perature, salinity, turbidity, dissolved oxygen, heavy metals), genetic composition (microsatellites, ITS‐2), abundance and biomass (wet and

Advances in paediatrics in 2019: Current practices and challenges in allergy, endocrinology, gastroenterology, public health, neonatology, nutrition, nephrology, neurology, respiratory diseases and rheumatic diseases

1- growth in preterm infants; 2- syndrome of inappropriate secretion of antidiuretic hormone; 3- adrenal hemorrhage; 4- type 1 diabetes.. Since early postnatal growth of preterm

The Solution Report Form

Any remaining solid can be washed out with small portions of ice cold water (as small as possible, as the compound possesses a slight solubility in water, and the losses of

A solitary pink lesion: dermoscopy and RCM features of lichen planus

Pilot study on reflectance confocal microscopy imaging of lichen planus: a real- time, non-invasive aid for clinical diagnosis. J Eur

Molecular analysis of a male breast cancer patient with prolonged stable disease under mTOR/PI3K inhibitors BEZ235/everolimus

Here we described a male breast cancer patient who received combination therapy of the dual PI3K/mTOR inhibitor BEZ235 and low-dose everolimus as a third-line treatment for

Search for hc →π+π-J /ψ via ψ (3686) →π0π+π-J /ψ

Cosmology, Ministry of Education; Shanghai Key Laboratory for Particle Physics and Cosmology; Institute of Nuclear and Particle Physics, Shanghai 200240, People ’s Republic of China..

2 Modules over a P.I.D. and Matrix Normal Form 15

We observe that if A has index 1, then every integral vector which is a rational linear combination of the rows of A is already an integral linear combination of the rows of A, that