✦ LIBER ✦

THE AMBIGUOUS TYPE THEORY IS HEREDITARILY UNDECIDABLE

✍ Scribed by Andrey A. Kuzichev

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 84 KB
Volume: 38
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.19920380126

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The ambiguous type theory ATT is introduced in [1] in order to obtain a new proof of Specker's theorem on typical ambiguity [3]. In the present paper we imbed the recursively undecidable theory TR of a single transitive‐reflexive relation in an arbitrary stratified theory T such that T ⫅ ATT and so reduce the problem of derivability in TR to the same problem for T. From this it follows that ATT is hereditarily undecidable, i.e. ATT has no decidable subtheories.

📜 SIMILAR VOLUMES

The theory of 〈N, +, Vk, Vl〉 is undecida

The theory of 〈N, +, Vk, Vl〉 is undecidable

✍ Roger Villemaire 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 783 KB

The first-order theory of linear one-ste

The first-order theory of linear one-step rewriting is undecidable

✍ Ralf Treinen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 758 KB

The theory of one-step rewriting for a given rewrite system R and signature C is the firstorder theory of the following structure: its universe consists of all C-ground terms, and its only predicate is the relation "x rewrites to y in one step by R". The structure contains no function symbols and no

The theory of idempotent semigroups is o

The theory of idempotent semigroups is of unification type zero

✍ Franz Baader 📂 Article 📅 1986 🏛 Springer Netherlands 🌐 English ⚖ 182 KB

Reduction of arithmetic to logic based o

Reduction of arithmetic to logic based on the theory of types without the axiom of infinity and the typical ambiguity of arithmetical constants

✍ Ludwik Borkowski 📂 Article 📅 1958 🏛 Springer Netherlands 🌐 English ⚖ 507 KB

Different effects of the two types of sp

Different effects of the two types of spatial pre-cueing: what precisely is “attention” in Di Lollo’s and Enns’ substitution masking theory?

✍ I. Luiga; T. Bachmann 📂 Article 📅 2006 🏛 Guilford Publishing Inc 🌐 English ⚖ 276 KB