Probabilistic Shoenfield Machines

Maksymilian Bujok 
Coordinator of the Computer Science Program 
Uniwersytet SWPS / SWPS University
Faculty of Design
Warsaw, Poland

Adam Mata
Ph.D. Candidate, Warsaw University of Technology Doctoral School.
Warsaw Poland

Wed, January 15, 2025 - 4:00 PM
Streaming on Zoom
In Hannan 108 (Auditorium)

During the seminar, we present the theoretical framework of Probabilistic Shoenfield Machines (PMS), which are an extension of the classical Shoenfield machine that models
randomness in the computational process. PMS are utilized in contexts with insufficient deterministic computations, such as randomized algorithms.

The concept of PMS is based on performing computations with specified probabilities,
enabling PMS to solve problems and make decisions based on probabilistic outcomes. We
provide an overview of PMS, detailing their formal definitions, the computation mechanisms,
and equivalence to nondeterministic Shoenfield machines.

If you have any questions about the Colloquium Series, would like to request disability accommodations  or would like to make a donation please contact the Physics Department, cua-physics@cua.edu or  call (202) 319-5315.