On a Solution and a Generalization of the Cigarette Smokers' Problem,
Abstract
The author of the Cigarette Smokers' Problem (S. Patil, MIT) tried to show that the problem could not be solved using Dijkstra's P- and V-operations without conditional statements. D. L. Parnas (CMU) showed that Patil's proof was false by presenting a solution using P- and V-operations, but no conditional statements. The paper presents first a correctness proof of Parnas' solution. This solution leads to an obvious generalization and in connection with it the question of an optimal set of distinguishable codewords is addressed. Finally a more natural approach to the problem is discussed and a solution for this variation is presented with its correctness proof. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1972
- Accession Number
- AD0750539
Entities
People
- Nico Habermann
Organizations
- Carnegie Mellon University