Generic undecidability of universal theories

摘要

Generic-case approach to algorithmic problems was suggestedby Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approachstudies behavior of an algorithm on typical (almost all) inputs and ignoresthe rest of inputs. In this paper we study generic complexity of undecidableuniversal theories.We prove that any undecidable universal theory remainsgenerically undecidable (i.e. for almost all inputs).