We prove that observational equivalence of 3rd-order finitary
Idealized Algol (IA) is decidable using Game Semantics. By
modelling state explicitly in our games, we show that the
denotation of a term M of this fragment of IA (built up from
finite base types) is a compactly innocent
strategy-with-state i.e. the strategy is generated by a
finite view function f_M. Given any such f_M, we
construct a real-time deterministic pushdown automata (DPDA) that
recognizes the complete plays of the knowing-strategy denotation
of M. Since such plays characterize observational equivalence,
and there is an algorithm for deciding whether any two DPDAs
recognize the same language, we obtain a procedure for deciding
observational equivalence of 3rd-order finitary IA. This
algorithmic representation of program meanings, which is
compositional, provides a foundation for model-checking a
wide range of behavioural properties of IA and other cognate
programming languages. Another result concerns 2nd-order IA with
full recursion: we show that observational equivalence for this
fragment is undecidable.
