Bio

Chris Phoumsavanh is an undergraduate student studying for his BE in mechatronics and robotics and BS in computer science and software engineering at Swinburne University of Technology in Melbourne, Australia. He is expecting to graduate in 2010, and his time at the university is being supported by the Vice Chancellor’s Scholarship in Engineering. As part of his university studies, he has spent time at the Defence Science and Technology Organisation (DSTO) investigating acoustic electric feedthrough communications and powering. His time at DSTO was supported by the DSTO Industry Experience Program.

He has attended similar summer schools, including the 32nd Professor Harry Messel International Science School (ISS2003), the 33rd ISS (ISS2005, as staff), and the 8th China Synergy Programme for Outstanding Youth (CSP8).

Project: Partial Solutions to the “Firing Squad Synchronisation Problem” using NKS

The “Firing Squad Synchronisation Problem” (FSSP) is a cellular automata (CA) problem first proposed by John Myhill in 1957. A solution was first found in the early 1960s.

To understand the FSSP, consider the following scenario: Consider a line (of arbitary length) of finite state machines known as “soldiers”, which at t = 0 are initialized to the same state with the exception of the leftmost machine, also known as the “General”. For every time step, the state of each machine is dependent only on the state of its two neighbors in the previous step (t–1). It should be noted that the General and the rightmost soldier each have only one neighbor on which their states can depend. Additionally, a soldier may not change its state if the state of itself and its neighbours is the initial state. The problem now is to define a set of rules that satisfy the above criteria, and ultimately to have each soldier (and the General) simultaneously reach a certain special “fire” state for the first time i.e.; this fire state should never be reached by any individual soldier before any other soldier. As stated above, a solution was first found in the early 1960s. In 1988 Mazoyer found a six-state solution and proved that there cannot be a four-state solution, though the question of a five-state solution still exists.

This project aims to use NKS principles to find partial solutions to the FSSP. For the purposes of this project, a partial solution is defined as a CA where all the soldiers reach the fire state though not necessarily simultaneously. A metric for how well a partial solution performs is the number of time steps required for all the soldiers to reach the fire state after any single soldier enters it. Another performance metric is how many soldiers reach the fire state, as it is not known whether all CAs will evolve to the point where all soldiers fire. Additionally, a metric may also be developed involving mapping the time differential versus the number of soldiers fired, on a two-dimensional graph.

Favorite Three-Color Cellular Automaton

Rule 1494957704718