"The brontosaurus moved deeper into the swamps when the mammals took over the forest, but one day it ran out of swamps."


BRINGING THE THEORY OF COMPUTATION TO PRIMARY & SECONDARY SCHOOL CHILDREN ....




DEMYSTIFYING THE MONSTERS OF THE THEORY OF COMPUTATION


THE PROOF OF THE PUDDING IS IN THE EATING





A wee bit about myself and my environment


HINTS AND SOLUTIONS TO GATE QUESTIONS ON THE THEORY OF COMPUTATION for GATE students in INDIA


CONTENTS: A partial finite enumeration of ceritfiable, positive and progressive associations with concepts/ideas/environments/organisations/people over a period of 5 years (2001-2005), created to escape the internet, pc, communications,globalisation, y2k and software offshoring revolutions in India and the attendent collapse of the ambitious indigenous self reliant computer industry, and this page has been primarily created to study indexing in the upcoming internet search engines.


EXPERIMENTS IN SEARCH OF COMMON SENSE
THE PROOF OF THE PUDDING IS IN THE EATING

"If we choose, we can live in a world of comforting illusion"---attributed to Noam Chomsky in The Times of India, 5 Nov 2006.



IN THE SEVENTIES PROF. C A R HOARE,FRS VISITED INDIA. WHILE STROLLING ON THE LAWNS OF TIFR, BOMBAY,  HE POINTED OUT THAT CONCEPTS IN COMPUTER SCIENCE WERE BASICALLY VERY SIMPLE,  THEY HAD BEEN MADE ARTIFICIALLY DIFFICULT AND THAT HE WOULD SPEND THE REST OF HIS LIFE MAKING THEM SIMPLE.




DRAFT----BEING CONTINUOUSLY UPDATED.
THE IDEAS WILL BE COHERENTLY ORGANISED IN DUE COURSE.


THE GOEDEL TURING SOCIETY WAS FORMED TO MAKE THE CONCEPTS OF THE THEORY OF COMPUTATION UNDERSTOOD BY COMMON SENSE EXPLANATIONS. AS PART OF THIS PROJECT EXPERIMENTS ARE BEING CONDUCTED WITH B.TECH/BE/MCA/MSC STUDENTS IN THEIR FINAL YEAR TO EXAMINE ANEW THE CONCEPTS OF THE THEORY OF COMPUTATION FROM A COMMON SENSE ANGLE. THIS EXPERIMENT HAS NOW BEEN TRIED OUT ON A COUPLE OF THOUSAND STUDENTS. THE LEVEL OF THEORY OF COMPUTATION HAS BEEN CHOSEN TO BE THE GATE LEVEL REQUIREMENTS OF THE THEORY OF COMPUTATION. THE GATE IS AN ENTRY LEVEL QUALIFYING EXAMINATION CONDUCTED IN INDIA FOR ADMISSION TO SOME OF THE LEADING INSTITUTIONS. THE STANDARD TEXT FOR THE SAME USED IS THE CINDERELLA BOOK(OLD VERSION).


THE PROOF OF THE PUDDING IS IN THE EATING


BEAR IN MIND THAT THE AUDIENCE CONSISTS OF STUDENTS DRAWN PRIMARILY FROM A FEUDAL AGRARIAN SOCIETY WITH JUST A TRACE OF EXPOSURE TO THE INDUSTRIAL AND INFORMATION REVOLUTIONS. THE CULTURAL BACKGROUND OF THE STUDENTS IS SMALL TOWN AND RURAL AND MAY LACK THE SLICKNESS OF MAJOR URBAN ENVIRONMENTS. THE ECONOMIC ENVIRONMENT MAKES ONLY ACCESS TO A COMMON PC COMMON RATHER THAN RARE.



THE PROOF OF THE PUDDING IS IN THE EATING


THE BASIC LONG TERM AIM OF THE BULK OF THE AUDIENCE IS A DECENT JOB WITH A DECENT MATERIALISTIC LIFE. THE STARS ARE NOT THE TARGET BUT FOR A HANDFUL OF THE STUDENTS.



THE PROOF OF THE PUDDING IS IN THE EATING



INITIAL SUCCESS WITH ENGINEERING STUDENTS LED TO EXPERIMENTS TO BRING THE CONCEPTS TO INTERMEDIATE STUDENTS. THE EXPERIMENTS WERE CONDUCTED AT M J COLLEGE OF ENGINEERING HYDERABAD FROM 2006-2011.
STUDENTS WERE DRAWN FROM THE INTERIOR REGIONS SURROUNDING THE TWIN CITIES OF HYDERABAD AND SECUNDERABAD.

THE PROOF OF THE PUDDING IS IN THE EATING





IT TOOK ME TWENTY YEARS TO REALLY ACCEPT THAT PROF.C.A.R. HOARE'S COMMENT IS VALID VERY MUCH EVEN FOR THE AREAS OF THE ANALYSIS OF ALGORITHMS AND THE THEORY OF COMPUTATION.
THE PROOF OF THE PUDDING IS IN THE EATING


IN MY EXPERIMENTS I HAVE MODELS USED FOR UNDECIDABILITY, COMPUTATIONAL COMPLEXITY AND INTRACTABIITY TO MAKE THE CONCEPTS COMMON SENSE AND TRIVIAL. THE RATIONAL MODELS ARE BASED ON THE GOLDEN GOOSE OF THE EXACT COVER PROBLEM. A GREAT DEAL OF THE MATHEMATICS OF COMPUTATION CAN BE EXPLAINED BY INSTANTANEOUS DESCRIPTIONS. THESE CAN BE CONSIDERED TO BE MODELING THE OUTSOURCING SITUATION OR A ANCIENT CLASSIC PRODUCTION OF SNOW WHITE AND THE SEVEN DWARFS. THE EXACT COVER PROBLEM CAN BE USED AS A SCAFFOLDING FOR ALL SUCH COMPUTATIONS. THE PROOFS AND CONSTRUCTIONS HAVE ONLY BEEN TACKLED FOR A COUPLE OF DOZEN PROBLEMS. I ANTICIPATE THAT IN A FEW YEARS TIME TO A DECADE OF TIME I SHOULD HAVE FIGURED OUT THE REQUIRED COMMONSENSE EXPLANATIONS WHICH MAY BE VALID IN MY ENVIRONMENT.


THE PROOF OF THE PUDDING IS IN THE EATING





THE PROOF OF THE PUDDING IS IN THE EATING


COMMON SENSE DEPENDS ON THE ENVIRONMENT, THE CULTURAL BACKGROUND, THE GEOGRAPHIC LOCATION, THE ECONOMIC LEVELS ETC ETC. SO WHAT IS COMMON SENSE IN ONE PART OF THE WORLD MAY NOT APPLY IN SOME OTHER PART OF THE WORLD.


THE PROOF OF THE PUDDING IS IN THE EATING




THE PROOF OF THE PUDDING IS IN THE EATING



A MAJOR SOURCE OF COMMON SENSE EXPLANATIONS IS TO REDUCE THE RIGOR WITH WHICH A PROBLEM IS STATED OR A PROOF IS EXPLAINED. ANOTHER MAJOR SOURCE WHICH HAS AN ENORMOUS USE IN THE THEORY OF COMPUTATION IS TO DRAW PARALLELS FROM THE LOCAL MYTHS, LEGENDS AND FOLKLORE.


THE PROOF OF THE PUDDING IS IN THE EATING





THE PROOF OF THE PUDDING IS IN THE EATING



A MAJOR ATTEMPT IS MADE TO EXPLAIN COOK'S THEOREM AND REDUCIBILITY AMONG COMBINATORIAL PROBLEMS. THE METHOD FOLLOWED IS GIVEN IN DETAIL: CLICK HERE. A MAJOR SOURCE OF COMMON SENSE EXPLANATIONS IS TO REDUCE THE RIGOR WITH WHICH A PROBLEM IS STATED OR A PROOF IS EXPLAINED. ANOTHER MAJOR SOURCE WHICH HAS AN ENORMOUS USE IN THE THEORY OF COMPUTATION IS TO DRAW PARALLELS FROM THE LOCAL MYTHS, LEGENDS AND FOLKLORE. ANOTHER MAJOR SOURCE USED IS TO USE A FEW FULLY WORKED OUT EXAMPLES EXPLAINING THE REDUCIBILITY AMONG 60 COMBINATORIAL PROBLEMS IN GREAT DETAIL USING A GENERIC DYNAMIC PROGRAMMING ALGORITHM.


THE PROOF OF THE PUDDING IS IN THE EATING



THE PROOF OF THE PUDDING IS IN THE EATING


NONDETERMINISM, COMPUTATIONAL COMPLEXITY AND INTRACTABILITY BECOME TRIVIAL COMMONSENSE CONCEPTS IF WE BEND RATIONALISM A WEE BIT, IN ANY CULTURE OR RELIGION. A WEE BIT OF ACCEPTED LEGENDS AND MYTHOLOGY FROM ANY CULTURE WILL DO. GRANT THE JINN OF THE MIDDLE EAST, THE RAKSHASAS, ASURAS OF HINDUISM, THE DRUIDS AND FAIRIES AND A TRANSFORMATION TO THIS ILLUSORY WORLD WORKS WONDERS. JUST LIKE THE FOURIER TRANSFORM AND LAPLACE TRANSFORM. WHEN THE MATHEMATICS OF COMPUTATION HAS TO BE EXPLAINED TO MILLIONS OF ORDINARY PEOPLE THIS CAN BE EXCUSED. OUR TARGET AUDIENCE IS THE MASS OF SOFTWARE PERSONNEL INVOLVED IN OUTSOURCING.


THE PROOF OF THE PUDDING IS IN THE EATING




THE PROOF OF THE PUDDING IS IN THE EATING




THE PROOF OF THE PUDDING IS IN THE EATING

JUST MODEL THE CAPABILITY OF A STUDENT BY A RECURSIVE FUNCTION AND A LOT OF COMPUTATIONAL COMPLEXITY IS EVIDENT. THIS MAY NOT BE ACCEPTABLE IN SOME ENVIRONMENTS WHICH HAVE OVERDONE RACISM, BUT IS ACCEPTABLE IN MANY CULTURES.

THE PROOF OF THE PUDDING IS IN THE EATING



JUST HAVE OUR MASCOT STUDENT ASK FOR A HANDLOAN FROM EACH ONE OF HIS CLASSMATES AND THE RESULTS WILL SHOW THE CLASSIC DIFFERENCE BETWEEN THE R.E. SETS AND RECURSIVE SETS, THE CONCEPT OF THE HALTING PROBLEM ETC.
THE PROOF OF THE PUDDING IS IN THE EATING


JUST CONSIDER HOW A ORDER IS PLACED WITH THE WAITER/STEWARD IS AN EATING HOUSE WITH A LARGE MENU AND WE CAN MODEL IT BY GENERATORS AND ACCEPTORS.
THE PROOF OF THE PUDDING IS IN THE EATING


A MAJOR APPLICATION OF AUTOMATA AND FORMAL LANGUAGE THEORY IS THE AREA OF CONSTRUCTION OF COMPILERS. THE TENDENCY IS TO MAKE THE SUBJECT SO THEORETICAL THAT UTTER CONFUSION REIGNS IN THE MIND OF THE STUDENT. A COMMON SENSE TREATMENT OF THE SUBJECT IS BASED ON THE HISTORIC TEXT "COMPILER CONSTRUCTIONS FOR DIGITAL COMPUTERS". THE ALGORITHMIC ADVANCES IN THE AREA LEND THEMSELVES TO COMMON SENSE EXPLANATIONS. A STILL MORE COMMON SENSE AND USER FRIENDLY APPROACH IS TO USE THE RAILWAY SHUNTING YARD ALGORITHM AS A PROLOGUE TO SYNTAX DIRECTED COMPILERS.THE STANDARD DRAGON BOOK HAS BEEN ATTEMPTED ONLY IN THE THIRD PASS THROUGH THE COURSE.
THE PROOF OF THE PUDDING IS IN THE EATING





THE PROOF OF THE PUDDING IS IN THE EATING


A DIFFICULT LEGENDARY PROOF IS THE ONE STUDYING THE COMPLEXITY OF THE UNION FIND ALGORITHM. IF WE CONSIDER A COMMON SENSE INTERPRETATION OF THE PROBLEM THE PROOF SEEMS OBVIOUS. START WITH THE 4 BILLION PERSONS ON EARTH AS SINGLETON BUSINESS VENTURES. CONSIDER MERGERS OF BUSINESSES, ORGANISATIONS. THE WEIGHTING RULE SAYS THE SMALLER GANG JOINS THE BIGGER ONE. THE COLLAPSING FIND MODELS EVERYONE IN THE ORGANISATION AS WANTING TO REPORT DIRECTLY TO THE CEO. AS THE SEQUENCE OF UNION FIND OPERATIONS PROCEEDS WE SEE THE BUSINESSES AND ORGANISATIONS UNFOLD AS IN ANY LARGE COUNTRY OR GROUP OF COUNTRIES.THE ENTIRE PROOF LENDS ITSELF TO A NICE QUALITATIVE USER FRIENDLY GRAPHICAL PRESENTATION. SEE HEREpresentations on algorithms.
THE PROOF OF THE PUDDING IS IN THE EATING


A DIFFICULT ALGORITHM IS THE ONE RELATED TO KLEENE'S THEOREM. IT IS CLASSIFIED AS DIFFICULT IN MOST STANDARD TEXTS. CHANGE THE SETTING TO THE WORLD OF A CHILD HAVING TO TRAVEL FROM HOME TO CLASS AND WANTING TO KNOW THE PATHS. START WITH DIRECT PATHS AND THEN HAVE THE MUNICIPALITY DEVELOP PARKS TO DIVERT THE CHILD. A DETAILED SIMULATION WITH A THREE NODE GRAPH WITH ALL THE INSTANTANEOUS DESCRIPTIONS MAKES THE THEOREM JUST PLAIN COMMON SENSE. SEE HEREpresentations on algorithms.
THE PROOF OF THE PUDDING IS IN THE EATING


THE CHOMSKY HIERARCHY CAN BE EASILY EXPLAINED BY AN ILLUSORY EXAMPLE. THIS USES SPACE COMPLEXITY AS THE BACKGROUND. TYPE 0 LANGUAGES CAN BE LIKENED TO AN ESSAY ORIENTED EXAMINATION WITH UNLIMITED TIME AND ANSWER SCRIPTS. FOR UNLIMTED PAPER USE THE MODEL OF GROWING AUTOMATA. LIMITING TIME AND IN A WAY SPACE CAN YIELD THE RECURSIVE FUNCTIONS.TYPE 1 LANGUAGES CAN BE MODELED BY OBJECTIVE TYPE EXAMINATIONS LIKE GRE AND TOEFL WITH ONE SHEET OF PAPER. THE DIFFICULTY OF THE CLASSIC PROBLEM OF CLOSURE OF CSLS UNDER COMPLEMENT BECOMES INTUITIVELY OBVIOUS. THE TYPE 3 LANGUAGES ARE A MODEL FOR ORAL EXAMINATIONS, WITH THE INK BEING CONFISCATED FROM THE TURING MACHINE. THE TYPE 2 LANGUAGES CAN BE CONSIDERED TO BE A MODEL OF THE PROTOCOL REQUIREMENTS OF VARIOUS LEVELS OF GUESTS AT A FORMAL FUNCTION WITH AN AUDITOR THROWN IN. EVERY CONTEXT FREE LANGUAGE IS THE INTERSECTION OF A DYCK LANGUAGE AND A REGULAR SET(roughly speaking). SEE HEREpresentations on algorithms.
THE PROOF OF THE PUDDING IS IN THE EATING


AS ANY COMPUTATION CAN BE CONSIDERED TO BE A MODEL FOR SIMULATING ANY OTHER COMPUTATION, ANY INTERPRETATION OF A COMPUTATION CAN BE TAKEN. WE CHOOSE THE INTERPRETATIONS WHICH ARE COMMONSENSE FOR A PARTICULAR AUDIENCE. THE MAIN DIFFICULTY IS THAT THE INTERPRETATIONS ARE NOT REUSABLE. WHAT IS VALID FOR ONE AUDIENCE MAY BE OFFENSIVE TO ANOTHER AUDIENCE. EXAMPLES DRAWN FROM ILLUSORY WORLD OF POPULAR CARTOON CHARACTERS AND THE WORLD OF CHILDREN ARE SAFEST. IF THE POPULAR CARTOON CHARACTERS ARE COPYRIGHT AND PATENTED THEN ONE CAN USE THE FABLES, FOLKLORE IN A LOCAL OR GLOBAL CONTEXT. SOMETIMES THE STANDARD CARICATURES OF POLITICIANS, GOONS, GOOD AND BAD CHARACTERS ALSO ALLOW USER FRIENDLY, COMMON SENSE EXPLANATIONS. THE ANIMAL WORLD IS RICH PROVIDING SEMANTCS FOR MANY CONCEPTS AND CONSTRUCTS. SEE HEREpresentations on algorithms.
THE PROOF OF THE PUDDING IS IN THE EATING


A TOOL THAT HAS PROVED ITSELF TO BE USEFUL IS TO CONVERT THE CONSTRUCTIONS OF GRAMMARS AND AUTOMATA TO DETAILED POWER POINT PRESENTATIONS. THE DETAIL HAS TO BE IN EXCRUCIATING DETAIL. THIS INVOLVES HUNDREDS TO A THOUSAND SLIDES PER PRESENTATION, AKIN TO THE CLASSIC DISNEY CARTOON MOVIES.SEE HEREpresentations on algorithms.
THE PROOF OF THE PUDDING IS IN THE EATING


THE PRESENTATIONS HAD TO BE HIGHLY GRAPHICAL, VERY COLORFUL AND USE SEMANTICS FOR THE SYMBOLS USED. A MAJOR USE OF SYMBOLS IS PRESENT IN AUTOMATA THEORY AND FORMAL LANGUAGES. IT IS NECESSARY THAT THE ABSTRACTION PRESENT IN THE SYMBOLS BE DILUTED BY INTERPRETATION. THIS IS AKIN TO THE USE OF SEMANTICS ASSOCIATED WITH SYMBOLS IN SYNTAX DIRECTED TRANSLATION, THE TRANSITION FROM HTML TO XML OR THE USE OF SEMANTICS AND ATTRIBUTES IN CONSTRAINT DATA BASES. THE USE OF THIS SEMANTICS IS LIKE THE USE OF A CATALYST IN CHEMICAL REACTIONS. THE SEMANTICS IS BASED UPON AN INTERPRETATION OF THE PROBLEM INVOLVED.
THE PROOF OF THE PUDDING IS IN THE EATING


IN THE CASE OF A DFA OR NFA ONE CAN USE THEM AS MODELS FOR THE BEHAVIOUR OF A CHILD. THE CHILD CAN BE IN THE PARK, HOME OR CLASS. THE TRANSITIONS CAN BE ON A GOOD MOOD OR BAD MOOD. SUCH A MODEL IS UNIVERSAL, FREE FROM STEPPING ON ANY CULTURAL TOES.

THE TRANSITION ON THE EMPTY STRING IN A FA CAN BE LIKENED TO A HITCHHIKERS FREE RIDE.A TRUE SYMBOL IS WHERE PAYMENT IS REQUIRED FOR THE RIDE. THE CLOSURE ON THE EMPTY STRING TURNS OUT TO BE THE HITCHHIKERS WORLD. SUCH A INTERPRETATION ALLOWS THE SYMBOLS USED IN THE REPRESENTATION TO HAVE SEMANTICS ASSOCIATED WITH THEM. THE SEMANTICS CAN BE VERBALISED OR CAN JUST BE THE UNSAID, UNVERBALISABLE ASSOCIATIONS IN THE CULTURAL ENVIRONMENT.
THE PROOF OF THE PUDDING IS IN THE EATING


THE CLASSIC MINIMISATION OF FINITE AUTOMATA BY THE PARTITIONING ALGORITHM CAN BE MODELED AS SIMULATING CLOSELY THE BREAKUP OF THE JOINT FAMILY SYSTEM IN INDIA AS A RESULT OF THE INDUSTRIAL AND INFORMATION REVOLUTIONS.
THE PROOF OF THE PUDDING IS IN THE EATING


INTERPRETATIONS FROM SOCIAL NETWORKING MAKE THE SEEMINGLY CLEVER, COMPLICATED PROOFS AND CONSTRUCTIONS OF REDUCTION AMONG A LARGE CLASS OF COMBINATORIAL PROBLEMS SEEM OBVIOUS AND BASED ON COMMON SENSE.
THE PROOF OF THE PUDDING IS IN THE EATING


SOME SORT OF A SILVER BULLET IS NEEDED FOR THE EXPLANATIONS DEALING WITH PUSH DOWN AUTOMATA AND TURING MACHINES. FOR THIS PURPOSE THE METHOD FOLLOWED DECADES AGO IN DABSE ON PCS IS USEFUL. THERE A QUERY BY EXAMPLE FOR USED. THE SAME TECHNIQUE CAN BE FOLLOWED FOR PDAS AND TMS.
THE PROOF OF THE PUDDING IS IN THE EATING


FOR CFGS, CFL, DCFLS, LR(K) GRAMMARS, PDA, DPDA, DERIVATIONS, AMBIGUITY ETC ETC IT TURNS OUT A SINGLE EXAMPLE SUFFICES TO INTRODUCE THE CONCEPTS. CONSIDER A GRAMMAR FOR EXPRESSIONS IN A PROGRAMMING LANGUAGE LIKE C. THE GRAMMAR ONLY DEALS WITH IDENTIFIERS AS SINGLE SYMBOLS AND USE THE ADDITION OPERATOR ONLY. CARE IS TAKEN REGARDING THE EOF SYMBOL. A DIRECT CONSTRUCTION FOR A LR(0) PARSER FOR A SUITABLE GRAMMAR IS CONSIDERED IN DETAIL. THE INSTANTANEOUS DESCRIPTIONS OF THE PARSER ARE CONSIDERED IN EXCRUCIATING DETAIL. THIS IS REPEATED WITH THE DPDA SHOWN AS A DPDA IN THE DIAGRAMS OF THE INSTANTANEOUS DESCRIPTIONS.
THE PROOF OF THE PUDDING IS IN THE EATING


THE PALINDROME LANGUAGE WHICH IS SO CENTRAL TO CFLS AND PDAS HAS A PLETHORA OF INTERPRETATIONS WHICH ARE OBVIOUS AND USER FRIENDLY IN ANY ENVIRONMENT.

THE MODIFICATIONS OF THE TURING MACHINE LENDS ITSELF TO MANY MODELS WHICH TURN OUT TO BE LABORIOUS TO CONSTRUCT. INTUITIVE EXPLANATIONS ARE NORMALLY USED. THIS DOES NOT HELP. WHAT WAS TAKEN WAS A SIMPLE LANGUAGE OF N A'S FOLLOWED BY N B'S. FOR THIS A DETAILED CONSTRUCTION WAS DONE BY OBTAINING THE INSTANTANEOUS DESCRIPTIONS FOR BLANK TAPE, MULTITAPE, TWO DIMENSIONAL, TWO PUSHDOWN TAPE, FOUR COUNTER AND TWO COUNTER MACHINES. SUCH A DEMONSTRATION BY EXAMPLE SEEMS NECESSARY.
THE PROOF OF THE PUDDING IS IN THE EATING


A SIMILAR DETAILED SIMULATION BY IDS IS WARRANTED FOR COOK'S THEOREM. TWO STANDARD MODELS ARE USED. ONE DEALS WITH THE RASP MODEL. WE CAN TAKE FOUR BIT MACHINES. A PROGRAM COMPARES TWO VARIABLES AND BASED ON THE RESULT INCREMENTS ONE OF THE VARIABLES NONDETERMINISTICALLY. THE ENTIRE CONSTRUCTION FOLLOWED IN COOK'S THEOREM IS SIMULATED STEP BY STEP IN A POWER POINT PRESENTATION PREPARED IN ABOUT 60 HOURS TIME. THE OTHER METHOD USED IS TO USE A NDTM WITH ONLY ONE CELL WITH A SYMBOL, TWO STATES. AN INTERPRETATION CAN EASILY BE FOUND WHICH IS USER FRIENDLY. THE CONSTRUCTION IS SIMULATED IN DETAIL.
THE PROOF OF THE PUDDING IS IN THE EATING


FOR UNDECIDABILITY THE FAMOUS THEOREM THAT THE COMPUTATIONS OF A TURING MACHINE CAN BE SIMULATED BY THE INTERSECTION OF TWO CFLS IS USED. THE PDAS INVOLVED CAN BE SIMULATED BY THE EXACT COVER PROBLEM. ACTUALLY WHAT IS USED IS A MODIFICATION OF THE EXACT COVER PROBLEM. WE CALL IT THE HYBRID COVER PROBLEM. IT IS A CROSS BETWEEN THE SET COVER PROBLEM AND EXACT COVER PROBLEM AND DRAWS SOME IDEAS FROM CONSTRAINT DATA BASES. IT CAN HOWEVER BE REDUCED TO THE EXACT COVER PROBLEM.
THE PROOF OF THE PUDDING IS IN THE EATING


PCP CAN VISUALLY AND GRAPHICALLY BE REPRESENTED IN OUR HYBRID COVER PROBLEM. THIS ALLOWS SOME MORE RESULTS FROM UNDECIDABILITY.
THE PROOF OF THE PUDDING IS IN THE EATING


THE LONG UBIQUITOUS TRAINS AND RAILWAY STATIONS IN INDIA ARE A RICH SOURCE FOR COMMON SENSE EXPLANATIONS OF MANY PROBLEMS, CONSTRUCTIONS AND PROOFS. THE PROBLEM OF DOVETAILING CAN BE LIKENED TO RECEIVING A RELATIVE IN SOME TRAIN. WITH THE CONSTRAINTS BEING VERY LONG TRAINS AND A VERY LARGE NUMBER OF PLATFORMS. THE ADVENT OF DIESEL AND ELECTRIC LOCOMOTIVES DO NOT MAKE THE SHUNTING YARDS VISIBLE NOWADAYS.
THE PROOF OF THE PUDDING IS IN THE EATING


ONE OF THE REQUIREMENTS IS THAT ABOUT 20 FORMAL LANGUAGES HAVE TO BE CLASSIFIED. THIS CAN BE AUGMENTED BY ANOTHER 20. THE CLASSIFICATION IS TO BE DONE AS PER THE CHOMSKY HIERARCHY. TWO METHODS USED ARE THE CONSTRUCTION OF AUTOMATA AND THE USE OF THE PUMPING LEMMA.
THE PROOF OF THE PUDDING IS IN THE EATING


EXPLAINING THE PUMPING LEMMA HAS THE DIFFICULTY OF HAVING TO DISTINGUISH BETWEEN NECESSARY CONDITIONS VERSUS NECESSARY AND SUFFICIENT CONDITIONS.

THE LEVELS OF THE PUMPING LEMMA: THE WEAK FORM, THE MEDIUM FORM AND THE STRONG FORM, CAN BE LIKENED TO THE SECURITY CHECKS OF DIFFERENT LEVELS FOR A TERRORIST. ALTERNATIVELY THEY CAN REPRESENT THE DIFFERENT LEVELS OF INSPECTION OF A AN ACADEMIC, INDUSTRIAL, GOVERNMENT OR MILITARY ORGANIZATION BY SOME STATUTORY BODY.
THE LONG STRING USED IN THE APPLICATION OF THE PUMPING LEMMA CAN BE LIKENED TO A LONG TRAIN. THE PROOFS ARE BEST EXPLAINED BY HAVING ONE OR TWO SLIDING WINDOWS MOVE OVER THE ENTIRE STRING.

THE PROOF OF THE PUDDING IS IN THE EATING


THE NORMAL TENDENCY OF TEXT BOOKS IS TO TREAT ONE OR TWO SCORE STANDARD FORMA LANGUAGES OF INTEREST AS CONSISTING OF DRY SYMBOLS. COMMON SENSE EXPLANATIONS DEMAND THE SYMBOLS BE GIVEN SOME ATTRIBUTES OR SEMANTICS. IN ANY NATURAL LANGUAGE WHEN THE ALPHABET IS EXPLAINED TO A CHILD A CHART IS USED FOR THIS PURPOSE. IN ENGLISH WE HAVE—A.SEMANTICS=”APPLE” AND SO ON TILL Z.SEMANTICS=”ZEBRA”. IN THE INTERPRETATION OF FORMAL LANGUAGES WE HAVE FOUND IT USEFUL TO HAVE FORMAL LANGUAGES AS REPRESENTING THE TRAVELS OF SOME MASCOT EMPLOYED FOR THE SYLLABUS. HERE WE HAVE---A.SEMANTICS=AUTO/AIRPLANE RIDE, B.SEMANTICS=BUS/BOAT RIDE, C.SEMANTICS=CAR RIDE, D.SEMANTICS=DONKEY RIDE/DRUDGE WALKING. SIMILAR INTERPRETATIONS ARE GIVEN THE A BINARY OR TERNARY ALPHABET.
THE PROOF OF THE PUDDING IS IN THE EATING


THIS ALLOWS RESTATEMENT OF THE DULL ABSTRACT FORMAL LANGUAGES AS:-
1) ALL JOURNEYS WITH AN EQUAL NUMBER OF AUTO RIDES AND BUS RIDES. (NOT FINITE, NOT REGULAR, CONTEXT FREE).
2) ALL JOURNEYS WITH A NUMBER OF AUTO RIDES FOLLOWED BY AN EQUAL NUMBER OF BUS RIDES. (NOT FINITE, NOT REGULAR, CONTEXT FREE).
3) ALL JOURNEYS WITH AN EQUAL NUMBER OF AUTO, BUS AND CAR RIDES IN ANY ORDER. (NOT FINITE, REGULAR).
4) ALL JOURNEYS WITH A NUMBER OF AUTO RIDES, FOLLOWED BY AN EQUAL NUMBER OF BUS RIDES, FOLLOWED BY AN EQUAL NUMBER OF CAR RIDES. (NOT FINITE, NOT REGULAR, NOT CONTEXT FREE, CONTEXT SENSITIVE).
5) ANY NUMBER OF BUS RIDES. (REGUAR).
6) AUTO RIDES, FOLLOWED BY BUS RIDES, FOLLOWED BY CAR RIDES, FOLLOWED BY DONKEY RIDES. AUTO RIDES SHOULD BE THE SAME NUMBER AS CAR RIDES AND BUS RIDES THE SAME NUMBER A DONKEY RIDES. (NOT REGULAR, NOT CONTEXT FREE, CONTEXT SENSITIVE). 7) THE NUMBER OF AUTO RIDES EITHER A PRIME, OR EXPONENTIAL, OR A PERFECT SQUARE, OR THE FACTORIAL OF SOME INTEGER. (NOT REGULAR, NOT CONTEXT FREE, CONTEXT SENSITIVE).
8) FINITE NUMBER OF RIDES OF SOME TYPES. (FINITE SET)
9) DO NOT TRAVEL. (EMPTY SET).
10) ALL JOURNEYS WITH AUTO RIDES FOLLOWED BY BUS RIDES. EITHER ONE OR TWO BUS RIDES FOR EVERY AUTO RIDE. (CONTEXT FREE BUT NOT DETERMINISTIC CONTEXT FREE).
11) ANY NUMBER OF AUTO RIDES FOLLOWED BY ANY NUMBER OF BUS RIDES.(REGULAR)
12) ANY NUMBER OF AUTO RIDES, FOLLOWED BY ANY NUMBER OF BUS RIDES, FOLLOWED BY ANY NUMBER OF CAR RIDES. (REGULAR).
13) ANY NUMBER OF AUTO RIDE, FOLLOWED BY ANY NUMBER OF BUS RIDES, FOLLOWED BY ANY NUMBER OF CAR RIDES AND FINALLY FOLLOWED BY ANY NUMBER OF DONKEY RIDES.(REGULAR).
ANOTHER INTERPRETATION DEALS WITH THE PALINDROME LANGUAGES AND THEIR VARIATIONS. THE ANIMAL KINGDOM IS A RICH SOURCE OF SYMBOLISM WITH SEMANTICS. IT IS ALSO A CULTURE FREE SOURCE FOR COMMONSENSE INTERPRETATIONS. CONSIDER THE ARRIVAL OF ANIMALS AT THE WATERHOLE. (SEE THE ONLINE REALTIME VIDEOS OF THE WATERHOLES IN THE AFRICAN JUNGLES).
14) NO ANIMAL TURNS UP AT THE WATERHOLE. (EMPTY SET).
15) A SOLITARY LION IS AT THE WATERHOLE.(FINITE SET).
16) A FINITE HERD OF ELEPHANTS AT THE WATERHOLE.(FINITE SET).
17) AN INFINITE HERD OF GIRAFFES AT THE WATERHOLE.(REGULAR).
18) AN INFINITE NUMBER OF ANIMALS ARRIVE AT THE WATERHOLE IN ANY ORDER.(REGULAR).
19) THE ORDER IN WHICH THE ANIMALS ARRIVE AT THE WATERHOLE TODAY IS THE SAME AS THE ORDER THEY ARRIVED YESTERDAY.(CONTEXT SENSITIVE NOT CONTEXT FREE).
20) THE ANIMALS COME TODAY IN THE REVERSE OF YESTERDAY’S ORDER OF ARRIVAL.(CONTEXT FREE, PERHAPS DCFL).
21) TODAY’S ORDER OF ARRIVAL FOLLOWS YESTERDAY’S ORDER. WE DO NOT KNOW WHEN YESTERDAY’S ORDER STOPPED AND TODAY’S STARTED. (NOT DETERMINISTIC CONTEXT FRE BUT CONTEXT FREE).
PALINDROMES ARE PERHAPS A BETTER COMMONSENSE EXPLANATION OF THE LAST THREE. THE ORDER OF ARRIVAL CAN BE RELATED TO PROTOCOLS TO BE FOLLOWED FOR GUESTS AT A FORMAL FUNCTION. THIS AUGMENTED BY FINITE AUTOMATA ALLOWS USER FRIENDLY CONSTRUCTIONS OF SOME AUTOMATA.
THE PROOF OF THE PUDDING IS IN THE EATING


TO THE ABOVE LIST COULD BE ADDED, WITH SUITABLE INTERPRETATIONS----
22) THE UNION OF SOME OF THE ABOVE LANGUAGES.
23) THE INTERSECTION OF SOME OF THE ABOVE LANGUAGES 24) THE COMPLEMENT OF THE ABOVE LANGUAGES.
25) THE COMBINATIONS OF UNION, INTERSECTION AND COMPLEMENT OF SOME OF THE ABOVE LANGUAGES.
26) EXTENSIONS TO SOME OPERATIONS ON LANGUAGES. COMMON SENSE EXPLANATIONS FOR THE OPERATIONS USED.

THE PROOF OF THE PUDDING IS IN THE EATING


A CLASSIC COMPILATION OF INTRACTABLE PROBLEMS BY SOME EXPERTS HAS AN INTERESTING COMMENT. IN THEIR EXPOSITION OF REDUCABILITY AMONG COMBINATORIAL PROBLEMS THEY SAY THEY HAVE FOUND IT EASIER TO DEVELOP THEIR OWN PROOFS RATHER THAN UNDERSTANDING THE PUBLISHED PROOF. THIS SHOWS THAT THE USE OF FORMALISM HAS BEEN OVERDONE. THE SYMBOLS AND FORMALISM ARE STATIC, AND THEY SHOULD PREFERABLY DENOTE SOME SEMANTICS BY SOME COMMONSENSE INTERPRETATION.
THE PROOF OF THE PUDDING IS IN THE EATING


WHEN THE COMPUTATION OF ANY COMPUTATIONAL DEVICE CAN BE DESCRIBED BY A SEQUENCE INSTANTANEOUS DESCRIPTIONS WE CAN USE THE EXACT COVER OR HYBRID COVER PROBLEM TO MODEL THE SAME. THE ONLY CONSTRAINT BEING THAT ONLY A FINITE PORTION OF ONE ID BE CHANGED INTO A FINITE PORTION OF THE SUCCEEDING ID. THIS OCCURS IN TURING MACHINE COMPUTATIONS, RAM AND RASP COMPUTATIONS, COMPUTATION MODELED BY FORMAL GRAMMARS ETC. ETC. ONE CAN FURTHER DESCRIBE THESE BY SAYING THE VALID COMPUTATIONS ARE DESCRIBED BY THE INTERSECTION OF TWO CONTEXT FREE LANGUAGES. THIS ALLOWS A LOT OF UNDECIDABILITY RESULTS TO BE DESCRIBED VISUALLY IN A USER FRIENDLY MANNER.
THE PROOF OF THE PUDDING IS IN THE EATING



THE PROOF OF THE PUDDING IS IN THE EATING


THE FEEDBACK (2000-2006)WAS THAT THE STUDENTS IN ENGINEERING FOUND THE SUBJECT TO BE UNDERSTANDABLE AND USER FRIENDLY. SOME FOUND IT VERY INTERESTING. MANY CLEARED THE GATE EXAMINATION AND SWAMPED THE HIGHER TIER INSTITUTIONS.

THE PROOF OF THE PUDDING IS IN THE EATING


THE FEEDBACK FROM THE INTERMEDIATE STUDENTS BASED ON EARLIER ATTEMPTS WAS NOT GOOD. SEE MECHANICAL NON-PC ORIENTED METHODS.

THE PROOF OF THE PUDDING IS IN THE EATING


THE FEEDBACK ON THE RECENT PC ORIENTED PRESENTATIONS METHOD HAS TO BE CONSOLIDATED AND EXPERIMENTED FURTHER. REFINEMENTS OF THE PRESENTATIONS, SIMPLIFICATION OF THE EXPLANATIONS, BETTER COMMON SENSE CHOICES ARE BEING ATTEMPTED.

THE PROOF OF THE PUDDING IS IN THE EATING


ALL ALGORITHMS OVER THE LAST HALF A CENTURY HAVE BEEN STUDIED WITH STATIC INPUT DATA. DYNAMICALLY VARYING DATA IS CALLED FOR IN EXPOSITIONS OF THE CONCEPTS OF THE THEORY OF COMPUTATION. A STATIC TABLE FOR THE EXACT COVER PROBLEM CAN MODEL THE RECURSIVE FUNCTIONS, FOR THE R.E. SETS A DYNAMICALLY GROWING OR VARYING TABLE IS IN ORDER. THIS IS MERELY A WATERED DOWN APPLICATION OF CONSTRAINT DATA BASES.

THE PROOF OF THE PUDDING IS IN THE EATING


A LOT OF REDUCTIONS AMONG COMBINATORIAL PROBLEMS CAN BE MADE SIMPLER BY USING THE HYBRID COVER PROBLEM AS AN INTERMEDIATE STAGE. THE MAPPING OF A NDTM COMPUTATION DIRECTLY TO THE NP-COMPLETE PROBLEM CAN BE CONSIDERED.

HOWEVER A FUNDAMENTAL RULE FOLLOWED IS THAT THE AIM IS NOT TO REWRITE OR CHANGE THE STANDARD CLASSIC TEXTS. THE METHODS, PROOFS AND CONCEPTS FOLLOWED THERE ARE TO BE EXPLAINED. THE CLASSIC TEXTS ARE TO BE TREATED AS THE HOLY WRIT.

THE PROOF OF THE PUDDING IS IN THE EATING



THE EXPOSITION OF A COMPUTER SCIENCE OR SOFTWARE ENGINEERING AREA CAN BE LIKENED TO A COMPUTATION. HENCE TO A PIECE OF SOFTWARE. ITS QUALITY CAN BE STUDIED JUST LIKE A PIECE OF SOFTWARE.
THE PROOF OF THE PUDDING IS IN THE EATING


CONSIDER SOME REPRESENTATIVE QUALITIES OF SOFTWARE: CORRECTNESS, UNDERSTANDAILITY, PORTABILITY, PERFORMANCE, RELIABILITY, REUSABILITY, INTEROPERABILITY, MAINTAINABILITY, VISIBILITY, VERIFIABILITY, ROBUSTNESS, PRODUCTIVITY AND USER FRRIENDLINESS. LET THESE QUALITIES BE MAPPED TO THE CINDERELLA BOOK.
THE PROOF OF THE PUDDING IS IN THE EATING


OVER THE LAST THREE DECADES I HAVE FOUND ONLY THREE TYPOGRAPHICAL ERRORS IN THE CINDERELLA BOOK OF 1979. SO THIS SHOWS EXTRAORDINARY HIGH RELIABILITY, ROBUSTNESS AND CORRECTNESS OF THE SAME. ALL THE OTHER FACTORS CAN BE MAPPED.
THE TIMEINESS IS HIGH AS THE ONLY MAJOR FUNDAMENTAL CHANGES HAVE BEEN THE RESOLUTION OF FERMAT'S LAST THEOREM AND THE TRACTABILITY OF THE PRIMES.
THE ONLY DIFFICULTIES ARE UNDERSTANDABILITY, USERFRIENDLINESS AND VISIBILITY.
THE ENORMOUS DEGREE OF CORRECTNESS FOUND IN THE CINDERELLA BOOK, THE WHETSTONE COMPILER EXPOSITION, THE ART OF COMPUTER PROGRAMMING MAKE THEM THE PILLARS OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING. PROF HOARE POINTED OUT THAT WE ARE VERY LUCKY TODAY WITH THE RELIABILITY OF OUR HARDWARE. THE SAME APPLIES TO THE WORKS OF THE SMALL BAND OF MEMBERS OF THE INVISIBLE COLLEGE OF COMPUTER SCIENCE AND SOFTWARE ENGINEERING. NO FORMAL VERIFICATION SEEMS NECESSARY FOR THEIR WORK.

THE PROOF OF THE PUDDING IS IN THE EATING


THE VISIBILITY CAN BE MAPPED TO POPULARITY THE AREA GAINS AS A RESULT OF THE EXPOSITION.
TRADITIONAL EXPOSITIONS OF THE THEORY OF COMPUTATION HAVE MADE THE SUBJECT UNPOPULAR. IT IS NOT POSSIBLE TO SURVIVE IN THE SOFTWARE INDUSTRY AND USE THE WORDS "TURING MACHINE" OR "AUTOMATA". IT CALLS FOR A PROVEN AND ESTABLISHED LEVEL OF COMPETENCY IN INDUSTRIAL SOFTWARE BEFORE THE TERMS CAN BE USED.

THE PROOF OF THE PUDDING IS IN THE EATING


OUT METHOD ALLOWS UNDERSTANDABIITY, USER FRIENDLINESS AND THE AREA GAINS IN POPULARITY ON A MASS SCALE. THE DISADVANTAGES ARE MANY. IT IS NOT PORTABLE, ROBUST, CORRECT OR HIGHLY RELIABLE. A MAJOR DISADVANTAGE IS THAT THE TREATMENT DOES N0T EASILY SCALE UP TO COMPLEX CONSTRUCTIONS AND PROOFS.
THE METHODS ARE NOT PORTABLE OR HIGHLY INTEROPERABLE AS OF YET. IT IS HIGHLY VISIBLE IN THE SENSE OF POPULARITY GAINED FOR THE AREA WITH STUDENTS OF AVERAGE ABILITY.EXTENSITBILITY OF KNOWLEDGE IS POORER WITH THIS. SO THE MAINTAINABILITY IS POOR. THE TIMELINESS IS POOR WITH THE RAPIDLY CHANGING WORLD.

THE MAIN ADVANTAGE IS THAT AN ENVIRONMENT IS CREATED WHICH IS USERFRIENDLY AND FAMILIAR. THIS ALLOWS THE MONSTERS FROM THE AUTOMATA FAMILY TO BE TAMED AND STUDIED WITHOUT NEGATIVE THOUGHTS.

THE PROOF OF THE PUDDING IS IN THE EATING