Chapter 1 - The Need for the Depiction Of Time-Space Problems
1.1 My Motivation for Writing this Document
I have been working as a programmer and software designer for around five years now. One of the areas
where I feel there is a lack of understanding (in general) , is the area of time-space depiction of problems,
without bringing the physicality of those problems into consideration.
For example, we could build an MP3 player in several ways :
a) through software,
b) a combination of software and hardware, or
c) through hardware(digital logic) itself.
These 3 physicalities are the solution for the same problem (creating a music player that plays MP3 files) ,
and at a logical level, perform the exact same activities i.e. :
i) Take an MP3 file as an input,
ii) Read the MP3 file,
iii) Convert the contents of the MP3 file into audio.
All engineering disciplines have their share of experts, but there are very few people that can use
their expertise in any other field of logic. For example, a chip design engineer might be a "whiz" at her/his
profession, but this does not guarantee that she/he could write equally great software programs.
My intention is to discuss the creation and design of "logic" modules at an abstract level, so as to
enable people (read laymen) like me to think of logic design independant of their physical manifestations.
For example, a person who can write software should be able to understand the control flows involved in digital
logic design (chips) and vice-versa.
The next generation of computing provides various challenges for logicians :
i) Usage of Human DNA for computation,
ii) Modelling electronic circuits based on biological control flows (eg. embryonics),
iii) Artificial Intelligence, where a machine is made to perform complex computations that were earlier thought
to be only possible through human brains,
iv) Complex pattern matching, such as Computer Vision, photograph recognition software,
v) "Intelligent" medicine, where the human body's bio-chemical reactions are used to perform computations, to
cure/prevent dangerous diseases,
vi) Depiction and simulation of complex systems such as weather patterns, economical systems and even human
psychology.
Some generic problems that engineers face today (not necessarily mutually exclusive from the above) are :
i) Understanding of design issues,
ii) Compiler/Parser design,
iii) Complex Automata,
iv) Understanding how grammars can be used to design, analyze and implement any kind of logic, etc. etc.
These series of articles/chapters seek to provide a platform for logicians to implement/design complex logic for any
of the above kinds of systems (physical or mental).
1.2 Core Philosophy
There are primarily 2 variables that our physical universe deals with: Space and Time. In essence, any system
or process can be described in terms of sequences of events. The word "sequence" specifies time (which is relative),
and the word "events" specifies space.
A simple example shall illustrate this concept. Say you want to describe the process of travelling to some place, say
England (assuming, of course, the traveller is not currently in England). This process can be described by the following
steps :
i) Call the travel agent,
ii) Buy a ticket,
iii) Reach your city's airport at departure date and time,
iv) Board the flight at your city's airport,
v) Get off at England airport.
In the above example, the "space" is specified by each of the steps, and the "time" can be specified by the order in
which the steps are carried out.
Without the steps and the order of steps, the process would be incomplete. If any step is left out, the traveller
cannnot reach England. If the sequence of the steps is changed from i), ii), iii), iv), v) to i), ii), iii), v), iv),
the described process will not make sense, as you cannot get off at the England airport before boarding the flight for
England.
Formally, if the steps mentioned in the example above are S1, S2, S3, S4 and S5, the process of going to England can
be specified as followed :
S -> P
P -> s1 s2 s3 s4 s5
The 2 lines specified above can be specified as a grammar S, where S1, S2, S3, S4 and S5 are called terminals. P is
called a non-terminal. These 2 lines can be described as the rules of Grammar S.
In a nutshell, any process or system can be described as a sequence of terminals and non-terminals.
1.3 Notation
To introduce the readers to the notation to be used in these articles, a more advanced example is needed than the one
specified in section 1.2. Before that, we need to understand the various building blocks of logic and grammars.
Consider the following bunch of rules :
S -> A B C D
A -> s1 | s2
B -> s3
C -> s4
D -> s5
In the above grammar S: A, B, C and D are non-terminals. s1, s2, s3, s4, s5 are terminals.
The '|' symbol specifies an OR operation. This means that the non-terminal A can can accept either terminal s1 or s2.
The rule A -> s1 | s2 can also be specified as :
A -> s1
A -> s2
Let us take a closer look at this grammar.
1.3.1 Non-terminals (A, B, C, D)
Non-terminals are grammars in their own right, and are sequences of terminal symbols. They are introduced to
introduce modularity in the grammar S. If we do not use the non-terminals A, B, C and D, the rules for grammar S
would be as follows:
S -> s1 s3 s4 s5 | s2 s3 s4 s5
The above rule means that the grammar S can accept any of the following sequences of terminal symbols (s1 s3 s4 s5) and
(s2 s3 s4 s5).
As this method of creating grammars is very cumbersome for long and complex sequences of terminals with plenty of
OR operations in between, we create a terminal A that specifies the OR operation, and produce a new bunch of rules that
describes grammar S :
S -> A s3 s4 s5
A -> s1 | s2
or,
S -> A s3 s4 s5
A -> s1
A -> s2
1.3.2 Terminals (s1, s2, s3, s4, s5)
Terminals signify each concrete or "actual" event to the system. In the example in section 1.2, each "step" involved
in travelling to England is a terminal. All possible sequences of terminals that are subject to the rules specified by
the grammar in question specify the behaviour of a system or process (or for that matter, anything quantifiable in time
and space).
1.4 A More Advanced Example
Let us take another example that will further illustrate the concepts introduced in the last few sections.
The following steps specify the algorithm logically followed by any ATM machine when a user tries to withdraw
cash :
i) Accept the user's ATM card, (Step S1)
ii) If the media is not working, print a message and stop processing the user's transaction, (Step S2)
iii) If the media is working, ask the user for her/his password, (Step S3)
iv) Accept the password from the user, (Step S4)
v) Ask the user how much cash she/he wants to withdraw, (Step S5)
vi) Accept the cash input amount from the user, (Step S6)
vii) Send the user's card Id, password and cash withdrawal amount to the banking mainframe, (Step S7)
viii) Wait for reply from the mainframe, (Step S8)
ix) If the reply message from the mainframe says incorrect password, tell the user so and stop processing
the transaction, (Step S9)
x) If the reply message says "balance in account not enough", then tell the user so, and stop processing
the transaction, (Step S10)
xi) If all goes well and the reply message gives an affirmative response, then output the cash into the cash-box
for the user to collect, (Step S11)
xii) Tell the user to collect her/his ATM card from the slot. (Step S12)
The following grammar A specifies the above algorithm :
S -> A
A -> S1 B
B -> S2 S12 | S3 S4 S5 S6 S7 S8 C S12
C -> S9 | S10 | S11
Note : a) A, B and C are non-terminals.
b) S is simply used to specify the beginning rule of a grammar, i.e., the rule
to be considered first.
c) Note that the B and C non-terminals have been used to abstract the "OR" conditionals in steps, ii), iii),
ix), x) and xi). Refer to section 1.3.1 for understanding the usage/representation of non-terminals in grammars.
