Typability and Type Checking in the Second-Order Λ-Calculus Are Equivalent and Undecidable (Preliminary Draft)

We consider the problems of typability[1] and type checking[2] in the Girard/Reynolds second-order polymorphic typed λ-calculus, for which we use the short name "System F" and which we use in the "Curry style" where types are assigned to pure λ -terms. These problems have been considered and proven to be decidable or undecidable for various restrictions and extensions of System F and other related systems, and lower-bound complexity results for System F have been achieved, but they have remained "embarrassing open problems"[3] for System F itself. We first prove that type checking in System F is undecidable by a reduction from semi-unification. We then prove typability in System F is undecidable by a reduction from type checking. Since the reverse reduction is already known, this implies the two problems are equivalent. The second reduction uses a novel method of constructing λ-terms such that in all type derivations, specific bound variables must always be assigned a specific type. Using this technique, we can require that specific subterms must be typable using a specific, fixed type assignment in order for the entire term to be typable at all. Any desired type assignment may be simulated. We develop this method, which we call "constants for free", for both the λK and λI calculi.

A Direct Algorithm for the Type Interference in the Rank 2 Fragment of the Second--Order λ-Calculus

We study the problem of type inference for a family of polymorphic type disciplines containing the power of Core-ML. This family comprises all levels of the stratification of the second-order lambda-calculus by "rank" of types. We show that typability is an undecidable problem at every rank k ≥ 3 of this stratification. While it was already known that typability is decidable at rank ≤ 2, no direct and easy-to-implement algorithm was available. To design such an algorithm, we develop a new notion of reduction and show how to use it to reduce the problem of typability at rank 2 to the problem of acyclic semi-unification. A by-product of our analysis is the publication of a simple solution procedure for acyclic semi-unification.

Deterministic Computations Whose History Is Independent of the Order of Asynchronous Updating

Consider a network of processors (sites) in which each site x has a finite set N(x) of neighbors. There is a transition function f that for each site x computes the next state ξ(x) from the states in N(x). But these transitions (updates) are applied in arbitrary order, one or many at a time. If the state of site x at time t is η(x; t) then let us define the sequence ζ(x; 0); ζ(x; 1), ... by taking the sequence η(x; 0),η(x; 1), ... , and deleting each repetition, i.e. each element equal to the preceding one. The function f is said to have invariant histories if the sequence ζ(x; i), (while it lasts, in case it is finite) depends only on the initial configuration, not on the order of updates. This paper shows that though the invariant history property is typically undecidable, there is a useful simple sufficient condition, called commutativity: For any configuration, for any pair x; y of neighbors, if the updating would change both ξ(x) and ξ(y) then the result of updating first x and then y is the same as the result of doing this in the reverse order. This fact is derivable from known results on the confluence of term-rewriting systems but the self-contained proof given here may be justifiable.

Working Memory Networks for Learning Temporal Order, with Application to 3-D Visual Object Recognition

Working memory neural networks are characterized which encode the invariant temporal order of sequential events. Inputs to the networks, called Sustained Temporal Order REcurrent (STORE) models, may be presented at widely differing speeds, durations, and interstimulus intervals. The STORE temporal order code is designed to enable all emergent groupings of sequential events to be stably learned and remembered in real time, even as new events perturb the system. Such a competence is needed in neural architectures which self-organize learned codes for variable-rate speech perception, sensory-motor planning, or 3-D visual object recognition. Using such a working memory, a self-organizing architecture for invariant 3-D visual object recognition is described. The new model is based on the model of Seibert and Waxman (1990a), which builds a 3-D representation of an object from a temporally ordered sequence of its 2-D aspect graphs. The new model, called an ARTSTORE model, consists of the following cascade of processing modules: Invariant Preprocessor --> ART 2 --> STORE Model --> ART 2 --> Outstar Network.

Statistical properties of first-order bang-bang Pll with nonzero loop delay

A method to solve the stationary state probability is presented for the first-order bang-bang phase-locked loop (BBPLL) with nonzero loop delay. This is based on a delayed Markov chain model and a state How diagram for tracing the state history due to the loop delay. As a result, an eigenequation is obtained, and its closed form solutions are derived for some cases. After obtaining the state probability, statistical characteristics such as mean gain of the binary phase detector and timing error variance are calculated and demonstrated.

The role of the community service order and the suspended sentence in Ireland: a judicial perspective

Imprisonment is the most severe penalty utilised by the criminal courts in Ireland. In recent decades the prison population has grown significantly despite expressions both official and public to reduce the use of the sanction. Two other sanctions are available to the Irish sentencer which may be used as a direct and comparable sentence in lieu of a term of imprisonment namely, the community service order and the suspended sentence. The community service order remains under-utilised as an alternative to the custodial sentence. The suspended sentence is used quite liberally but its function may be more closely related to the aim of deterrence rather than avoiding the use of the custodial sentence. Thus the aim of decarceration may not be optimal in practice when either sanction is utilised. The decarcerative effect of either sanction is largely dependent upon the specific purpose which judges invest in the sanction. Judges may also be inhibited in the use of either sanction if they lack confidence that the sentence will be appropriately monitored and executed. The purpose of this thesis is to examine the role of the community service order and the suspended sentence in Irish sentencing practice. Although community service and the suspended sentence present primarily as alternatives to the custodial sentence, the manner in which the judges utilise or fail to utilise the sanctions may differ significantly from this primary manifestation. Therefore the study proceeds to examine the judges' cognitions and expectations of both sanctions to explore their underlying purposes and to reveal the manner in which the judges use the sanctions in practice. To access this previously undisclosed information a number of methodologies were deployed. An extensive literature review was conducted to delineate the purpose and functionality of both sanctions. Quantitative data was gathered by way of sampling for the suspended sentence and the part-suspended sentence where deficiencies were apparent to show the actual frequency in use of that sanction. Qualitative methodologies were used by way of focus groups and semi-structured interviews of judges at all jurisdictional levels to elucidate the purposes of both sanctions. These methods allowed a deeper investigation of the factors which may promote or inhibit such usage. The relative under-utilisation of the community service order as an alternative to the custodial sentence may in part be explained by a reluctance by some judges to equate it with a real custodial sentence. For most judges who use the sanction, particularly at summary level, community service serves a decarcerative function. The suspended sentence continues to be used extensively. It operates partly as a decarcerative penalty but the purpose of deterrence may in practice overtake its theoretical purpose namely the avoidance of custody. Despite ongoing criticism of executive agencies such as the Probation Service and the Prosecution in the supervision of such penalties both sanctions continue to be used. Engagement between the Criminal Justice actors may facilitate better outcomes in the use of either sanction. The purposes for which both sanctions are deployed find their meaning essentially in the practices of the judges themselves as opposed to any statutory or theoretical claims upon their use or purpose.

Within the carnal: re-reading Merleau-Ponty through the language of drawing

In order to present visual art as a paradigm for philosophy, Merleau-Ponty investigated the creative processes of artists whose work corresponded closely with his philosophical ideas. His essays on art are widely valued for emphasising process over product, and for challenging the primacy of the written word in all spheres of human expression. While it is clear that he initially favoured painting, Merleau-Ponty began to develop a much deeper understanding of the complexities of how art is made in his late work in parallel with his advancement of a new ontology. Although his ontology remains unfinished and only exists as working notes and a manuscript entitled The Visible and Invisible, Merleau-Ponty had begun to appreciate the fundamental role drawing plays in the making of art and the creation of a language of expression that is as vital as the written or spoken word. Through an examination of Merleau-Ponty’s unfinished manuscript and working notes my thesis will investigate his working methods and use of materials and also explore how he processed his ideas by using my own art practice as the basis of my research. This research will take the form of an inquiry into how the unfinished and incomplete nature of text and artworks, while they are still ‘works in progress’, can often reveal the more human and carnal components of creative processes. Applying my experience as a practitioner and a teacher in an art school, I focus on the significance of drawing practice for Merleau-Ponty’s later work, in order to rebalance an overemphasis on painting in the literature. Understanding the differences between these two art forms, and how they are taught, can offer an alternative engagement with Merleau-Ponty’s later work and his struggle to find a language to express his developing new ontology. In addition, by re-reading his work through the language of drawing, I believe we gain new insights which reaffirm Merleau-Ponty's relevance to contemporary art making and aesthetics.

First- and second-order phase transitions in the adlayer of biadipate on Au(111)

The adsorption of biadipate on Au(111) was studied by cyclic voltammetry and chronocoulometry. The biadipate adlayer undergoes a potential-driven phase transition. It is shown that the phase transition can be either of the first- or second-order depending on the biadipate concentration. At low surfactant concentrations, the first-order transition is characterised by a discontinuity in the charge density-potential curve and by the presence of very sharp peaks in the voltammetric response. At higher concentrations, these peaks are no longer observed but a discontinuity in the capacity curve is still noticeable, in agreement with a second-order transition. © the Owner Societies.

Probing polarization and dielectric function of molecules with higher order harmonics in scattering-near-field scanning optical microscopy

The idealized system of an atomically flat metallic surface [highly oriented pyrolytic graphite (HOPG)] and an organic monolayer (porphyrin) was used to determine whether the dielectric function and associated properties of thin films can be accessed with scanning-near-field scanning optical microscopy (s-NSOM). Here, we demonstrate the use of harmonics up to fourth order and the polarization dependence of incident light to probe dielectric properties on idealized samples of monolayers of organic molecules on atomically smooth substrates. An analytical treatment of light/sample interaction using the s-NSOM tip was developed in order to quantify the dielectric properties. The theoretical analysis and numerical modeling, as well as experimental data, demonstrate that higher order harmonic scattering can be used to extract the dielectric properties of materials with tens of nanometer spatial resolution. To date, the third harmonic provides the best lateral resolution (∼50 nm) and dielectric constant contrast for a porphyrin film on HOPG. © 2009 American Institute of Physics.

Control of the orientational order and nonlinear optical response of the "push-pull" chromophore RuPZn via specific incorporation into densely packed monolayer ensembles of an amphiphilic four-helix bundle peptide: characterization of the peptide-chromophore complexes.

"Push-pull" chromophores based on extended pi-electron systems have been designed to exhibit exceptionally large molecular hyperpolarizabilities. We have engineered an amphiphilic four-helix bundle peptide to vectorially incorporate such hyperpolarizable chromophores having a metalloporphyrin moiety, with high specificity into the interior core of the bundle. The amphiphilic exterior of the bundle facilitates the formation of densely packed monolayer ensembles of the vectorially oriented peptide-chromophore complexes at the liquid-gas interface. Chemical specificity designed into the ends of the bundle facilitates the subsequent covalent attachment of these monolayer ensembles onto the surface of an inorganic substrate. In this article, we describe the structural characterization of these monolayer ensembles at each stage of their fabrication for one such peptide-chromophore complex designated as AP0-RuPZn. In the accompanying article, we describe the characterization of their macroscopic nonlinear optical properties.

No-Holdback allocation rules for continuous-time assemble-to-order systems

This paper analyzes a class of common-component allocation rules, termed no-holdback (NHB) rules, in continuous-review assemble-to-order (ATO) systems with positive lead times. The inventory of each component is replenished following an independent base-stock policy. In contrast to the usually assumed first-come-first-served (FCFS) component allocation rule in the literature, an NHB rule allocates a component to a product demand only if it will yield immediate fulfillment of that demand. We identify metrics as well as cost and product structures under which NHB rules outperform all other component allocation rules. For systems with certain product structures, we obtain key performance expressions and compare them to those under FCFS. For general product structures, we present performance bounds and approximations. Finally, we discuss the applicability of these results to more general ATO systems. © 2010 INFORMS.

The short and long of it: neural correlates of temporal-order memory for autobiographical events.

Previous functional neuroimaging studies of temporal-order memory have investigated memory for laboratory stimuli that are causally unrelated and poor in sensory detail. In contrast, the present functional magnetic resonance imaging (fMRI) study investigated temporal-order memory for autobiographical events that were causally interconnected and rich in sensory detail. Participants took photographs at many campus locations over a period of several hours, and the following day they were scanned while making temporal-order judgments to pairs of photographs from different locations. By manipulating the temporal lag between the two locations in each trial, we compared the neural correlates associated with reconstruction processes, which we hypothesized depended on recollection and contribute mainly to short lags, and distance processes, which we hypothesized to depend on familiarity and contribute mainly to longer lags. Consistent with our hypotheses, parametric fMRI analyses linked shorter lags to activations in regions previously associated with recollection (left prefrontal, parahippocampal, precuneus, and visual cortices), and longer lags with regions previously associated with familiarity (right prefrontal cortex). The hemispheric asymmetry in prefrontal cortex activity fits very well with evidence and theories regarding the contributions of the left versus right prefrontal cortex to memory (recollection vs. familiarity processes) and cognition (systematic vs. heuristic processes). In sum, using a novel photo-paradigm, this study provided the first evidence regarding the neural correlates of temporal-order for autobiographical events.

Life-narrative and word-cued autobiographical memories in centenarians: comparisons with 80-year-old control, depressed, and dementia groups.

Centenarians provided autobiographical memories to either a request for a life narrative or a request to produce autobiographical memories to cue words. Both methods produced distributions with childhood-amnesia, reminiscence-bump, and recency components. The life-narrative method produced relatively more bump memories at the expense of recent memories. The life-narrative distributions were similar to those obtained from 80-year-old adults without clinical symptoms and from 80-year-old Alzheimer's dementia and depression patients, except that the centenarians had an additional 20-year period of relatively low recall between the bump and recency components. The centenarians produced more emotionally neutral memories than the other three groups and produced fewer and less detailed memories than the non-clinical 80-year-old sample.

Properties of word cues for autobiographical memory.

A sample of 124 words were used to cue autobiographical memories in 120 adults varying in age from 20 to 73 years. Individual words reliably cued autobiographical memories of different ages with different speeds. For all age groups, words rated high in imagery produced older memories and faster reaction times.