Accession Number : AD0635056

Title :   STUDIES CONCERNING MINIMAL TIME SOLUTIONS TO THE FIRING SQUAD SYNCHRONIZATION PROBLEM.

Descriptive Note : Doctoral thesis.

Corporate Author : CARNEGIE INST OF TECH PITTSBURGH PA CENTER FOR THE STUDY OF INFORMATION PROCESSING

Personal Author(s) : Balzer, Robert M.

Report Date : 1966

Pagination or Media Count : 175

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)

Descriptors :   (*OPERATIONS RESEARCH, *MAN MACHINE SYSTEMS), MATHEMATICAL MODELS, PROBLEM SOLVING, MILITARY STRATEGY, OPTIMIZATION

Subject Categories : Operations Research
      Military Operations, Strategy and Tactics
      Human Factors Engineering & Man Machine System

Distribution Statement : APPROVED FOR PUBLIC RELEASE