6533b829fe1ef96bd1289772

RESEARCH PRODUCT

Amount of Nonconstructivity in Finite Automata

Rūsiņš Freivalds

subject

Discrete mathematicsProbabilistic methodDeterministic finite automatonKolmogorov complexityIntuitionismLimit (mathematics)Mathematical proofConstructiveMethod of conditional probabilitiesMathematics

description

When D. Hilbert used nonconstructive methods in his famous paper on invariants (1888), P.Gordan tried to prevent the publication of this paper considering these methods as non-mathematical. L. E. J. Brouwer in the early twentieth century initiated intuitionist movement in mathematics. His slogan was "nonconstructive arguments have no value for mathematics". However, P. Erdos got many exciting results in discrete mathematics by nonconstructive methods. It is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. R.Freivalds [7] showed that nonconstructive methods in coding theory are related to the notion of Kolmogorov complexity. We study the problem of the quantitative characterization of the amount of nonconstructiveness in nonconstructive arguments. We limit ourselves to computation by deterministic finite automata. The notion of nonconstructive computation by finite automata is introduced. Upper and lower bounds of nonconstructivity are proved.

yearjournalcountryeditionlanguage
2009-01-01
https://doi.org/10.1007/978-3-642-02979-0_26