[Colloquium] Theory speaker

[Donna Brooms]

THEORY SEMINAR

Tuesday, January 15, 2013

3:00 p.m.

Ryerson 251



Rusins Freivalds

Institute of Mathematics and Computer Science, University of Latvia
www.lza.lv/scientists/freivalds.htm

Title: “Ultrametric automata and Turing machines”

Abstract:
A notion of ultrametric automata and Turing machines using p-adic numbers is introduced 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.
There are many distinct p-adic absolute values corresponding to the many prime numbers p. These absolute values are traditionally called ultrametric. Absolute values are needed to consider distances among objects.  However, there is an important feature that distinguishes p-adic numbers from real numbers. Real numbers (both rational and irrational) are linearly ordered. p-adic numbers cannot be linearly ordered. This is why valuations and norms of p-adic numbers are considered.
The situation is similar in Quantum Computation. Quantum amplitudes are complex numbers which also cannot be linearly ordered. The counterpart of valuation for quantum algorithms is measurement translating a complex number a+bi into a real number a2+b2. Norms of p-adic numbers are rational numbers.
Host: Prof. Alexander Razborov

*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*

 

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20121228/cd9c9087/attachment-0001.htm