6533b86ffe1ef96bd12ce684

RESEARCH PRODUCT

Ultrametric Finite Automata and Turing Machines

Rūsiņš Freivalds

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceComputer scienceSuper-recursive algorithmProbabilistic Turing machineDescription numberNonlinear Sciences::Cellular Automata and Lattice GasesTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring completenesssymbolsQuantum finite automataAutomata theoryTwo-way deterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematicsofComputing_DISCRETEMATHEMATICS

description

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

yearjournalcountryeditionlanguage
2013-01-01
https://doi.org/10.1007/978-3-642-38771-5_1