Zapiski Nauchnykh Seminarov LOMI
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zap. Nauchn. Sem. POMI:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zapiski Nauchnykh Seminarov LOMI, 1979, Volume 88, Pages 131–136 (Mi znsl3108)  

This article is cited in 2 scientific papers (total in 2 papers)

A primitive recursive bound of strong normalization for predicate calculus

G. E. Mints
Full-text PDF (314 kB) Citations (2)
Abstract: Strong normalization theorem asserts convergence of any reduction (cutelimination) sequence. Most popular strong normalisation proofs use hereditary normalizability which cannot be expressed by an arithmetic formula, thus the resulting proof for the intuitionistic predicate calculus is not formalizable in arithmetic. There is a hope to adapt Howard's proof [1] using nonunique ordinal assignments to obtain primitive recursive proof of strong normalizability for $(\supset,\forall$)-fragment of predicate calculus but the author of this paper was unable to overcome combinatorial difficulties.
We obtain a primitive recursive bound for strong,normalization of $\lambda$-terms of finite types by reducing arbitrary reduction sequence to standard one (where innermost terms of maximal level are contracted first) and prove that the gain in the number of $s$ steps is not too big. Let $\nu(t)$ be the maximal length of reduction sequences for term $t$. First by recursion on $\omega^3$ we define function $\Psi$ estimating $\nu(t)$ in terms of $\nu(t')$ for $t\vdash t'$. Recursion on $\omega$ is known to be reducible to several ($\leq6$) primitive recursions. This allows us to define $\nu(t)$ in terms of $\nu(t')$, where $t\vdash t'$, by conversion of an innermost-subterm of the maximal level. In this way $\nu$ is defined from $\Psi$ by recursions. One cannot use less than 4 recursions for $\nu$ in veiw of Statman's lower bound (cf. also Orevkov's paper in this volume, cf. [3]) for normalization. It is to be seen what is exact bound for strong normalization.
English version:
Journal of Soviet Mathematics, 1982, Volume 20, Issue 4, Pages 2334–2336
DOI: https://doi.org/10.1007/BF01629443
Bibliographic databases:
UDC: 510.6
Language: Russian
Citation: G. E. Mints, “A primitive recursive bound of strong normalization for predicate calculus”, Studies in constructive mathematics and mathematical logic. Part VIII, Zap. Nauchn. Sem. LOMI, 88, "Nauka", Leningrad. Otdel., Leningrad, 1979, 131–136; J. Soviet Math., 20:4 (1982), 2334–2336
Citation in format AMSBIB
\Bibitem{Min79}
\by G.~E.~Mints
\paper A~primitive recursive bound of strong normalization for predicate calculus
\inbook Studies in constructive mathematics and mathematical logic. Part~VIII
\serial Zap. Nauchn. Sem. LOMI
\yr 1979
\vol 88
\pages 131--136
\publ "Nauka", Leningrad. Otdel.
\publaddr Leningrad
\mathnet{http://mi.mathnet.ru/znsl3108}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=556225}
\zmath{https://zbmath.org/?q=an:0429.03032|0492.03022}
\transl
\jour J. Soviet Math.
\yr 1982
\vol 20
\issue 4
\pages 2334--2336
\crossref{https://doi.org/10.1007/BF01629443}
Linking options:
  • https://www.mathnet.ru/eng/znsl3108
  • https://www.mathnet.ru/eng/znsl/v88/p131
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Statistics & downloads:
    Abstract page:185
    Full-text PDF :52
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024