STUDIES CONCERNING MINIMAL TIME SOLUTIONS TO THE FIRING SQUAD SYNCHRONIZATION PROBLEM.
Abstract
This paper presents a description of a general outline for a minimal time solution to the firing squad synchronization problem, and a solution of this form which is composed of machines with only eight states. The paper then discusses the verification of this minimal time solution by computer simulation, and gives a mathematical induction proof that the solution works for any length. The paper then discusses some efforts to determine the minimal number of states needed for a minimal time solution. No four state minimal time solution exists. A reasonable set of conditions are presented for which no five state minimal t time solutions exist. The final part of the paper demonstrates the equivalence of one-dimensional iterative arrays and turing machines, and shows how the techniques used here apply to problems of optimizing turing machines for a given computation. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1966
- Accession Number
- AD0635056
Entities
People
- Robert M. Balzer
Organizations
- Carnegie Institute of Technology