Languages And Machines - Notes for Math237

Author : Dr. Christopher D. H. Cooper, Division of Information and Communication Sciences, Macquarie University
Publication Date : July 2005

Book Excerpts:

The unifying theme in this book is the concept of a language as a system of strings of characters strings obeying certain rules. Strings are fundamental to computing science. Although we tend to think of computers as devices for manipulating numbers, words and pictures, it is more accurate to think of them as machines for manipulating strings of symbols which in turn represent numbers, words or pictures.

This book begins by discussing a special-purpose language - the language of logic. Then it develops a language for talking about languages in general. Since languages are just sets of strings, this book will talk about sets and the associated concepts of relations and functions, using yet another special-purpose language.

At this stage this book will also discuss proofs. It investigates the nature of proof from the syntactic point of view, that is, thinking of proofs as sequences of strings of symbols related to each other in a mechanical way. As well as helping readers to write sound mathematical proofs this book will give them some insight into automated proofs of program correctness.

This book will also teach the connection between languages and machines that manipulate them. Finite-state machines and Turing Machines are important mathematical models of the computing process and they are used to answer a number of important theoretical questions.

Finally this book will looks briefly at encryption and coding. Both of these involve transforming strings of symbols and are important applications to the computing and communications industries. At the same time, both make real use of interesting parts of mathematics - the mathematics of numbers and of polynomials.

View/Download Languages And Machines - Notes for Math237