Model Classification

Conceptual Model

A conceptual model can be described using various notations, such as UML or OMT for object modelling, or IE or IDEF1X for Entity Relationship Modelling. In UML notation, the conceptual model is often described with a class diagram in which classes represent concepts, associations represent relationships between concepts and role types of an association represent role types taken by instances of the modelled concepts in various situations. In ER notation, the conceptual model is described with an ER Diagram in which entities represent concepts, cardinality and optionalityrepresent relationships between concepts. Regardless of the notation used, it is important not to compromise the richness and clarity of the business meaning depicted in the conceptual model by expressing it directly in a form influenced by design or implementation concerns.








Abstract Model

Abstract model theory provides an approach that allows us to step back and study a wide range of logics and their relationships. The starting point for the study of abstract models, which resulted in good examples was Lindström's theorem.










Simulation Model

A simulation model is a mathematical model of a system or process that includes key inputs which affect it and the corresponding outputs that are affected by it. If the model explicitly includes uncertainty, we refer to it as a Monte Carlo simulation model. For example, it can calculate the impact of uncertain inputs and decisions we make on outcomes that we care about, such as profit and loss, investment returns, environmental consequences, and the like. Such a model can be created by writing code in a programming language, statements in a simulation modeling language, or formulas in a Microsoft Excel spreadsheet. Regardless of how it is expressed, a simulation model will include:
Model inputs that are uncertain numbers -- we'll call these uncertain variables
Intermediate calculations as required
Model outputs that depend on the inputs -- we'll call these uncertain functions


It's essential to realize that model outputs that depend on uncertain inputs are uncertain themselves -- hence we talk about uncertain variables and uncertain functions. When we perform a simulation with this model, we will test many different numeric values for the uncertain variables, and we'll obtain many different numeric values for the uncertain functions. We'll use statistics to analyze and summarize all the values for the uncertain functions (and, if we wish, the uncertain variables).






Heterogenous Model

The homogeneity hypothesis implies that the substitution process ultimately reaches an equilibrium and it is also assumed that the process was already stationary at the very beginning, i.e., at the root of the phylogeny. If the homogeneity and stationarity assumptions were true, equal nucleotide frequencies would be expected in past and present-day sequences. Actually, we can observe discrepancy's in nucleotide frequencies in many real data sets of present species: model assumptions are clearly violated when using real sequences.


It has been noticed that sequences of similar composition tend to be grouped together irrespective of their real phylogenetic relationships (Lockhart et al., 1994; Tarrio et al., 2001, see e.g., ). In an attempt to avoid this bias, we developed an HETEROGENEOUS model in a Bayesian framework which models coarsely the heterogeneity using a small pool of homogeneous processes. Each branch of the tree ``chooses'' a substitution model among them. The likelihood computation now depends on the position of the root which is why a heterogeneous rooted tree was implemented in PHASE (ultrametricity is optional). The composition observed at this root becomes a free parameter of the model (see, e.g., Yang and Roberts, 1995; Galtier and Gouy, 1998).


Algorithms developed in PHASE are very similar to those implemented in P4 by Peter Foster. PHASE framework might be a bit more general since the full substitution model is allowed vary over the tree. However, you are strongly advised to limit yourself to variation of the composition vector as Foster (2004) did. Unfortunately, we did not have time to implement a way to use a single exchangeability matrix over the whole tree yet. There is a workaround (a bit unsatisfactory): you can start the MCMC chain from a model properly initialized and turn off the perturbation of rate ratios so that they have constant values. Use the same trick to fix the gamma shape parameter and the proportion of invariant sites to a single constant value. (Do not use a +I model with HETEROGENEOUS without constraining the proportion of invariant sites to a constant value).


PHASE is missing an efficient MCMC proposal to modify the position of the root. You are advised to use an outgroup in the TREE block to constrain the position of the common ancestor. Remember that this outgroup can also be a monophyletic cluster.






Model Building Methodology

Model building methodologies are playing an increasingly significant role in many aspects of software engineering activities. Today models are being applied right from requirement conceptualization to the final software installation and maintenance. Traditional methodologies however, fail to cope with increasing complexity and rapidly evolving nature of the software. The need for an efficient model building methodology is quite manifest today. The main objective of this study is to propose and implement a novel Model Building Methodology utilizing Artificial Neural Network (ANN). In order to achieve this objective, information related to regression analysis was reviewed.

Simulation in used in the following Context

Simulations can be used to provide a fertile learning environment for students. The use of simulated activities in education is widely becoming recognized as an important tool in schools.


Educational simulations offer several benefits:

• Simulations are often cheaper to create than their real life counterparts. Installing flight simulation software is cheaper than buying a practice jet for each school.
• They are easier to construct
• Simulations remove the element of danger from the situation. For example, you can "interact" with a Bengal tiger in a simulation quite safely.
• Simulations can be paused, whereas real life cannot. Pausing allows more time for students to assess what's going on.

Activities that promote learning tend to meet the following criteria:

• They simulate an activity that is "real", and so it can be said that they are "virtually real". They simulate the activity so well that there is little difference between the simulated environment and the real one, and the same kind of learning experience can take place.
• They are "hands-on", involving students so they become participants, not mere listeners or observers. Students learn better from their own experiences than having others' experiences related to them.
• They are motivators for learning. Student involvement in the activity is so deep that interest in learning more about the activity or its subject matter develops.
• They are tailored to the student. When simulations are designed specifically for their audience, they can take developmental requirements into consideration.
• They are inspirational. Student input is welcome and activities are designed to encourage students to enhance the activity by contributing their own ideas.
• They are developmentally valid. Simulations take into account the students' developmental level.
• They are empowering. Students take on responsible roles, find ways to succeed, and develop problem solving tools as a result of the interaction.

The teacher's role used to be that of presenter of facts to students who absorb information like passive sponges. Most teachers will recognise that role as having changed. Simulations add a new dimension to teh learning experience and develop the teacher's role even further.

Input Data Analysis

Simulation Input Modeling

Discrete-event simulation models typically have stochastic components that mimic the probabilistic nature of the system under consideration. Successful input modeling requires a close match between the input model and the true underlying probabilistic mechanism associated with the system. The general question considered here is how to model an element (e.g., arrival process, service times) in a discrete-event simulation given a data set collected on the element of interest. For brevity, it is assumed that data is available on the aspect of the simulation of interest. It is also assumed that raw data is available, as opposed to censored data, grouped data, or summary statistics. Most simulation texts (e.g., Law and Kelton 1991) have a broader treatment of input modeling than presented here. Nelson et al. (1995) and Nelson and Yamnitsky (1998) survey advanced techniques. 1 COLLECTING DATA There are two approaches that arise with respect to the collection of data.

In this tutorial we first review introductory techniques for simulation input modeling. We then identify situations in which the standard input models fail to adequately represent the available input data. In particular, we consider the cases where the input process may (i) have marginal characteristics that are not captured by standard distributions; (ii) exhibit dependence; and (iii) change over time. For case (i), we review flexible distribution systems, while we review two widely used multivariate input models for case (ii). Finally, we review nonhomogeneous Poisson processes for the last case. We focus our discussion around continuous random variables; however, when appropriate references are provided for discrete random variables. Detailed examples will be illustrated in the tutorial presentation.

Input Data Collection

Data Collection Problems

• We are having a data collection issue for some of our accounts and are actively working on a fix.
• We have the problem mostly resolved and are fine tuning. Data collection may be bumpy as we tune the collection process.
• We appear to be having a bump in the road and are investigating.
• We’re hitting file handle limits that are taking everything down. We will switch back to a previous known working configuration.
• We’ve reverted to a previous configuration but are still seeing problems.
• The problem appears to have moved to our database tier. The UI is now affected for all customers.
• We have reverted back to a previous configuration and things are stabilizing. The database issue has been solved. The UI should be back.
• We have been stable now since 11:30am. We believe this incident is closed.

Over the past several weeks we’ve been moving our data collection tier over to a new system. The new system is designed to handle significantly more load than the existing one. The conversion had been going well until this incident. Testing revealed a design flaw, for which we put a fix in place. We will begin migrating to the new system again once we’re confident this problem won’t occur again. We apologize for the downtime.

Practical Suggestions

This section provides a number of practical suggestions to improve the capacity of organisations and individuals involved in Sport & Development.

Recognise potential risks

Experience shows that being aware of potential risks and taking suitable measures to anticipate them can help to avoid problems in the future. Attempts should be made to empathise with the constraints and challenges the local partner in its local situation faces. Experience shows that regarding sport as an integral part of the programme with a view of capacity building that incorporates sport and development elements, helps to ensure better quality programmes in the long-run with increased sustainability.

Attempt capacity building at all levels

Capacity building can be divided into interventions at three levels: Human Resource Development (HRD), Organisational Development (OD) and Institutional Development (ID). Good and sustainable capacity building is conditional upon investing in all three levels.

It is difficult for sport organisations to be active at all three levels but it is a necessity if one aims to improve the sustainability of a programme. It is difficult to negotiate with ministries for the recognition of diplomas, for supporting legislation (for example, physical education), so that trained sport instructors can work in schools. It can be useful to try to accomplish these tasks through networking with organisations that might use other methodology to reach an overall development goal.

As a consequence, in some countries the sport projects of sport and development organisations are ‘filling the gap’ in the lack of physical education on the school curriculum. Investments will therefore also have to be made at OD and ID levels in order to ensure these sport activities are sustainable and are used to achieve the objectives set at the initial stages of the programme.

A joint consultation process should take place to decide what changes are needed internally and what possibilities there are for institutional change. A possible next step can be networking with other stakeholders in the field and/or signing agreements with the local/national governments.

There are many examples of different forms of cooperation between organisations. For instance, KNVB and UNICEF offer their core capacities within the MYSA project, in which KNVB concentrates on activities in relation to football and UNICEF is responsible for guiding the elements of the programme that relate to social change.

Local ownership is essential

Many of the projects currently being implemented in Sport & Development are not locally owned. A cooperative relationship must be developed with a local partner organisation before starting a project.

Assessment of partners and potential of cooperation

It is important to assess capacities and resources of each organisation entering into a partnership before joining forces. Questions such as: “Do the organisations match in terms of mission and vision? What resources does each partner bring to the programme? Does the local partner organisation have the capacity to absorb the programme and what can other partners do to enhance this? What measures are in place to encourage learning and to share experiences between the partners involved?” should be asked before entering into a formal partnership.

A tool has been developed by Commonwealth Games Canada for the selection of a suitable partner: the Partnership Filter. Potential partners are screened on the basis of several criteria.

Go to the partnerships section to read more about this instrument: examples of how it can be used and advice is provided for selecting and successfully developing with partners.

Qualifications of trainers posted abroad

People who had been trained as sport leaders used to be sent abroad to implement Sport & Development programmes. Qualified staff need to be enlisted. Feedback from experts has shown that a shift is now taking place in the background of people who are posted overseas, with a decreasing focus on recruitment of unqualified staff.

Sustainability

Many projects train local people. This is capacity building at the level of HRD. Often the project ends after the training. But what happens next with the individual capacity that has been developed? Is it used by the partner organisation? Are more sport activities offered? To what extent does the target group take part? It is of great importance to monitor and evaluate the implementation that takes place after the training sessions and to plan measures in the design phase of projects and programmes that will lead to sustainability.

 

Effects of Period of Time

Many process related with human activities
are not stable even within small time periods.
• For example, arrivals rates in airports,
restaurants, banks will be significantly effected
by time of day.
• Period of time may not be important if we are
interested in a small portion of time period
(e.g. worst case scenario for times having
peak demans).
• If period of time is significant;
– Collect data from a whole range of different
time periods,
– Examine data collected, and
– Divide data into intervals for different time
periods if required.

Input Modeling Strategy

 Histograms

• A graphical display of tabulated frequencies (a set
of data intervals & sample counts for them).
• Data samples are commonly represented as times
for occurance of some events or completion of a
process.

• No definite rule to select correct histogram
parameters.
• Iterate through;
– Adjusting starting point and interval width,
– And setting the number of intervals to
cover all the data.
• Select an appropriate histogram for
representing the data samples.

• If interval widths are so large,
– Chart will be too coarse, and
– Details of the shape of the data will be lost.

• If interval widths are so small,
– Chart will be too noisy, and
– Overview of the shape of the data will be lost.
• There is no best histogram.
• As a suggestion try to cover at least 3 to 5
samples in each interval.

Probability Distribution

• Describes the values and probabilities
associated with a random event
(probability distribution function,
probability density function).

Selection of Probability Distribution

• Use a set of criteria to rank goodness of fit of
the fitted distributions to the data.
• If any of the top/ranked models are terribly
inconsistent with the range of limits of value,
rule them out.

• Use a reasonable set of criteria to determine
if the best of the fitted distributions is a
reasonable representation of data.
• If best one provides a reasonable
representation of data,
– Use it in simulation,
• Otherwise,
– Use an emperical distribution to represent
data directly.

Evaluating Goodness Of Fit

• Consider a number of measures of goodness
of fit rather than a single one
– Since each will be unrealible in some cases.

 • Do not depend on goodness of fit measures
– That rely on overly clean data samples (e.g.
ignored problematic samples) or
– On user supplied parameters (e.g.
histogram configurations).
– Since they can provide inconsistent results.

• In the context of simulation input modeling,
– Classical goodness of fit methods in
statistics are not completely appropriate for
final assessment of quality of fit.
– Statistical methods have definite
assumptions that are sometimes not true for
simulation modeling.
– So, graphical heuristic methods should also
be used to assess which is best and which
is good enough.

• For evaluation;
– Histograms, and
– Emperical cummulative probability
distribution function of sample data can be
used.

Church Turing Thesis

Turing Machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

The "Turing" machine was described by Alan Turing in 1936,^[1] who called it an "a(utomatic)-machine". The Turing machine is not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.

Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:

...an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.^[2] (Turing 1948, p. 61)

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'.

A Turing machine is an idealized computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.

The input that is inscribed on the tape before the computation starts must consist of a finite number of symbols. However, the tape is of unbounded length--for Turing's aim was to show that there are tasks that these machines are unable to perform, even given unlimited working memory and unlimited time.

The read/write head is programmable. It is be helpful to think of the operation of programming as consisting of altering the head's internal wiring by means of a plugboard arrangement. To compute with the device, you program it, inscribe the input on the tape (in binary or decimal code, say), place the head over the square containing the leftmost input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the leftmost symbol of the output (or elsewhere if so programmed).

States

The head contains a subdevice that I call the indicator. This is a second form of working memory. The indicator can be set to any one of a number of 'positions'. In Turing machine jargon, the position of the indicator at any time is called the state of the machine at that time. To give a simple example of the indicator's function, it may be used to keep track of whether the symbol last encountered was '0' or '1'. If '0', the indicator is set to its first position, and if '1', to its second position.

Atomic operations

There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:

• read (i.e. identify) the symbol currently under the head
• write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
• move the tape left one square
• move the tape right one square
• change state
• halt.

These are called the primitive or atomic operations of the machine. A complicated computation may consist of hundreds of thousands, or even millions, of occurences of these atoms

Commercially available computers are hard-wired to perform primitive operations considerably more sophisticated than those of a Turing machine--add, multiply, decrement, store-at-address, branch, and so forth. The precise constitution of the list of primitives varies from manufacturer to manufacturer. It is a remarkable fact that none of these computers can outdo a Turing machine. Despite the Turing machine's austere simplicity, it is capable of computing anything that any computer on the market can compute.

Indeed, since it is an abstract or notional machine, a Turing machine can compute more than any physical computer. This is because (1) the physical computer has access to only a bounded amount of memory, and (2) the physical computer's speed of operation is limited by various real-world constraints.

It is sometimes said, incorrectly, that a Turing machine is necessarily slow, since the head is continually shuffling backwards and forwards, one square at a time, along a tape of unbounded length. But since a Turing machine is an idealised device, it has no real-world constraints on its speed of operation.

The instruction table

A program or 'instruction table' for a Turing machine is a finite collection of instructions, each calling for certain atomic operations to be performed if certain conditions are met. Every instruction is of the form:

If the current state is n and the symbol currently under the head is x, then write y on the square currently under the head [y may be identical to x], go into state m [m may be n], and - - - .

In place of - - - may be written either 'move left one square' or 'move right one square' or 'halt'.

An example

The machine in this example starts work with a blank tape. The tape is endless. The problem is to set up the machine so that if the scanner is positioned over any square and the machine is set in motion, it will print alternating binary digits on its tape, 0 1 0 1 0 1..., working to the right from its starting place, and leaving a blank square in between each digit.

In order to do its work the machine makes use of four states, labelled 'a', 'b', 'c' and 'd'. The machine is in state a when it starts work.

The table of instructions for this machine is as follows.The top line of the table reads: if you are in state a and the square you are scanning is blank then print 0 on the scanned square, move right one square, and go into state b.

state	scanned symbol	print	move	next state
a	blank	0	R	b
b	blank		R	c
c	blank	1	R	d
d	blank		R	a

A machine acting in accordance with this table of instructions toils endlessly on, printing the desired sequence of digits and leaving alternate squares blank. 

Variants of Turing Machine 

Turing Machines are the simplest formally defined model which is capable of computing anything that modern computers can compute. This makes them useful for theoretical study. However, devising a Turing Machine that solves a given problem of interest is not always easy. Therefore, there exist several common variants of Turing Machines which have been proven to be equivalent in computational power to a Turing Machine, but provide much more flexibility by increasing the types of steps that can be added to an Turing Machine algorithm. Proofs that a computational model is equivalent in power to a Turing Machine generally involve showing how to construct a Turing Machine given any possible instance of the model. Sometimes devising an algorithm to solve a problem using one of these is far easier, and since we know that they can be converted to a Turing Machine, we don't need to do all that extra work.

A list of common Turing Machine variants, otherwise known as Turing Equivalent machines:

• Non Deterministic Turing Machine - A Turing Machine which may follow more than one transition per configuration.
• Multitape Turing Machine - A Turing Machine containing a finite number of tapes greater than 1.
• Universal Turing Machine - A Turing Machine that is able to store any other Turing Machine on its tape and emulates its function. This is also related to the Recursion Theorem and is one of the more broadly useful (and important) constructs in Computational Theory.
• Enumerator - A Turing Machine which has a printer attached and prints out lists of strings.

These are useful models in the Theory of Computation, but really any programming language which describes only algorithms (which is all of them, currently) could be considered a Turing Machine variant. Arbitrary languages tend to be far less useful for Theory than the aforementioned machines, so I don't list them.

Less Powerful Computational Models

Turing Machines can also describe less powerful models of computation which can solve subsets of the problems which Turing Machines can solve. These other models can be more practical in terms of hardware costs and implementation, and form the basis for the abundant simple electronic devices that far outnumber computers. Studying what these types of machines can solve is also important, because we can we can know more about their function in general than we can about Turing Machines. 

Hilbert's Problem

Hilbert's problems ranged greatly in topic and precision. Some of them are propounded precisely enough to enable a clear affirmative/negative answer, like the 3rd problem (probably the easiest for a nonspecialist to understand and also the first to be solved) or the notorious 8th problem (the Riemann hypothesis). There are other problems (notably the 5th) for which experts have traditionally agreed on a single interpretation and a solution to the accepted interpretation has been given, but for which there remain unsolved problems which are so closely related as to be, perhaps, part of what Hilbert intended. Sometimes Hilbert's statements were not precise enough to specify a particular problem but were suggestive enough so that certain problems of more contemporary origin seem to apply, e.g. most modern number theorists would probably see the 9th problem as referring to the (conjectural) Langlands correspondence on representations of the absolute Galois group of a number field. Still other problems (e.g. the 11th and the 16th) concern what are now flourishing mathematical subdisciplines, like the theories of quadratic forms and real algebraic curves.

There are two problems which are not only unresolved but may in fact be unresolvable by modern standards. The 6th problem concerns the axiomatization of physics, a goal that twentieth century developments of physics (including its recognition as a discipline independent from mathematics) seem to render both more remote and less important than in Hilbert's time. Also, the 4th problem concerns the foundations of geometry, in a manner which is now generally judged to be too vague to enable a definitive answer.

Remarkably, the other twenty-one problems have all received significant attention, and late into the twentieth century work on these problems was still considered to be of the greatest importance. Notably, Paul Cohen received the Fields Medal during 1966 for his work on the first problem, and the negative solution of the tenth problem during 1970 by Matiyasevich (completing work of Davis, Putnam and Robinson) generated similar acclaim. Aspects of these problems are still of great interest today.

Hilbert's twenty-three problems are:

Problem	Brief explanation	Status	Year Solved
1st	The continuum hypothesis (that is, there is no set whose cardinality is strictly between that of the integers and that of the real numbers)	Proven to be impossible to prove or disprove within the Zermelo–Fraenkel set theory with or without the Axiom of Choice (provided the Zermelo–Fraenkel set theory with or without the Axiom of Choice is consistent, i.e., contains no two theorems such that one is a negation of the other). There is no consensus on whether this is a solution to the problem.	1963
2nd	Prove that the axioms of arithmetic are consistent.	There is no consensus on whether results of Gödel and Gentzen give a solution to the problem as stated by Hilbert. Gödel's second incompleteness theorem, proved in 1931, shows that no proof of its consistency can be carried out within arithmetic itself. Gentzen proved in 1936 that the consistency of arithmetic follows from the well-foundedness of the ordinal ε0.	1936?
3rd	Given any two polyhedra of equal volume, is it always possible to cut the first into finitely many polyhedral pieces which can be reassembled to yield the second?	Resolved. Result: no, proved using Dehn invariants.	1900
4th	Construct all metrics where lines are geodesics.	Too vague to be stated resolved or not.[n 1]	–
5th	Are continuous groups automatically differential groups?	Resolved by Andrew Gleason, depending on how the original statement is interpreted. If, however, it is understood as an equivalent of the Hilbert–Smith conjecture, it is still unsolved.	1953?
6th	Axiomatize all of physics	Unresolved. [n 2]	–
7th	Is a b transcendental, for algebraic a ≠ 0,1 and irrational algebraic b ?	Resolved. Result: yes, illustrated by Gelfond's theorem or the Gelfond–Schneider theorem.	1935
8th	The Riemann hypothesis ("the real part of any non-trivial zero of the Riemann zeta function is ½") and other prime number problems, among them Goldbach's conjecture and the twin prime conjecture	Unresolved.	–
9th	Find most general law of the reciprocity theorem in any algebraic number field	Partially resolved.[n 3]	–
10th	Find an algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution.	Resolved. Result: impossible, Matiyasevich's theorem implies that there is no such algorithm.	1970
11th	Solving quadratic forms with algebraic numerical coefficients.	Partially resolved.[citation needed]	–
12th	Extend the Kronecker–Weber theorem on abelian extensions of the rational numbers to any base number field.	Unresolved.	–
13th	Solve all 7-th degree equations using continuous functions of two parameters.	Resolved. The problem was solved affirmatively by Vladimir Arnold based on work by Andrei Kolmogorov. [n 5]	1957
14th	Is the ring of invariants of an algebraic group acting on a polynomial ring always finitely generated?	Resolved. Result: no, counterexample was constructed by Masayoshi Nagata.	1959
15th	Rigorous foundation of Schubert's enumerative calculus.	Partially resolved.[citation needed]	–
16th	Describe relative positions of ovals originating from a real algebraic curve and as limit cycles of a polynomial vector field on the plane.	Unresolved.	–
17th	Expression of definite rational function as quotient of sums of squares	Resolved. Result: An upper limit was established for the number of square terms necessary.[citation needed]	1927
18th	(a) Is there a polyhedron which admits only an anisohedral tiling in three dimensions? (b) What is the densest sphere packing?	(a) Resolved. Result: yes (by Karl Reinhardt). (b) Resolved by computer-assisted proof. Result: cubic close packing and hexagonal close packing, both of which have a density of approximately 74%.[n 6]	(a) 1928 (b) 1998
19th	Are the solutions of Lagrangians always analytic?	Resolved. Result: yes, proven by Ennio de Giorgi and, independently and using different methods, by John Forbes Nash.	1957
20th	Do all variational problems with certain boundary conditions have solutions?	Resolved. A significant topic of research throughout the 20th century, culminating in solutions[citation needed] for the non-linear case.	–
21st	Proof of the existence of linear differential equations having a prescribed monodromic group	Resolved. Result: Yes or no, depending on more exact formulations of the problem.[citation needed]	–
22nd	Uniformization of analytic relations by means of automorphic functions	Resolved.[citation needed]	–
23rd	Further development of the calculus of variations	Unresolved.

Designing Finite Automata

The difference between Deterministic finite Automata and Non-Deterministic finita Automata

Deterministic Finite Automata
 
A DFA represents a finite state machine that recognizes a RE. For example, the following DFA:
 
 

recognizes (abc⁺)⁺. A finite automaton consists of a finite set of states, a set of transitions (moves), one start state, and a set of final states (accepting states). In addition, a DFA has a unique transition for every state-character combination. For example, the previous figure has 4 states, state 1 is the start state, and state 4 is the only final state.
A DFA accepts a string if starting from the start state and moving from state to state, each time following the arrow that corresponds the current input character, it reaches a final state when the entire input string is consumed. Otherwise, it rejects the string.
The previous figure represents a DFA even though it is not complete (ie, not all state-character transitions have been drawn). The complete DFA is:

but it is very common to ignore state 0 (called the error state) since it is implied. (The arrows with two or more characters indicate transitions in case of any of these characters.) The error state serves as a black hole, which doesn't let you escape.
A DFA is represented by a transition table T, which gives the next state T[s, c] for a state s and a character c. For example, the T for the DFA above is:
 

	a	b	c
0	0	0	0
1	2	0	0
2	0	3	0
3	0	0	4
4	2	0	4

 
Suppose that we want to build a scanner for the REs:

for - keyword	=	for
identifier	=	[a - z][a - z0 - 9]*

The corresponding DFA has 4 final states: one to accept the for-keyword and 3 to accept an identifier:

(the error state is omitted again). Notice that for each state and for each character, there is a single transition.
A scanner based on a DFA uses the DFA's transition table as follows:
 

state = initial_state;
current_character = get_next_character();
while ( true )
{   next_state = T[state,current_character];
    if (next_state == ERROR)
       break;
    state = next_state;
    current_character = get_next_character();
    if ( current_character == EOF )
       break;
};
if ( is_final_state(state) )
   `we have a valid token'
else `report an error'

 
This program does not explicitly take into account the longest match disambiguation rule since it ends at EOF. The following program is more general since it does not expect EOF at the end of token but still uses the longest match disambiguation rule.
 

state = initial_state;
final_state = ERROR;
current_character = get_next_character();
while ( true )
{   next_state = T[state,current_character];
    if (next_state == ERROR)
       break;
    state = next_state;
    if ( is_final_state(state) )
       final_state = state;
    current_character = get_next_character();
    if (current_character == EOF)
       break;
};
if ( final_state == ERROR )
   `report an error'
else if ( state != final_state )
   `we have a valid token but we need to backtrack
         (to put characters back into the input stream)'
else `we have a valid token'

 
Is there any better (more efficient) way to build a scanner out of a DFA? Yes! We can hardwire the state transition table into a program (with lots of gotos). You've learned in your programming language course never to use gotos. But here we are talking about a program generated automatically, which no one needs to look at. The idea is the following. Suppose that you have a transition from state s₁ to s₂ when the current character is c. Then you generate the program:
 

s1: current_character = get_next_character();
    ...
    if ( current_character == 'c' )
       goto s2;
    ...
s2: current_character = get_next_character();
    ...

Non-Deterministic Finite Automata

An NFA is typically described using a directed graph as shown in Figure 11.8b, and is considered as a special kind of finite state machine. Each vertex of the graph represents a state, and edges represent possible transitions. An input string of finite length is read by the machine. Typically, the input string is a binary sequence of 0's and 's. The initial state is designated by an inward arrow that has no source vertex, as shown pointing into state in Figure 11.8b. The machine starts in this state and reads the first symbol of the input string.

Based on its value, it makes appropriate transitions. For a DFA, the next state must be specified for each of the two inputs 0 and from each state. From a state in an NFA, there may be any number of outgoing edges (including zero) that represent the response to a single symbol. For example, there are two outgoing edges if 0 is read from state (the arrow from to actually corresponds to two directed edges, one for 0 and the other for ). There are also edges designated with a special symbol. If a state has an outgoing , the state may immediately transition along the edge without reading another symbol. This may be iterated any number of times, for any outgoing edges that may be encountered, without reading the next input symbol. The nondeterminism arises from the fact that there are multiple choices for possible next states due to multiple edges for the same input and transitions. There is no sensor that indicates which state is actually chosen.
 
The interpretation often given in the theory of computation is that when there are multiple choices, the machine clones itself and one copy runs each choice. It is like having multiple universes in which each different possible action of nature is occurring simultaneously. If there are no outgoing edges for a certain combination of state and input, then the clone dies. Any states that are depicted with a double boundary, such as state in Figure 11.8, are called accept states. When the input string ends, the NFA is said to accept the input string if there exists at least one alternate universe in which the final machine state is an accept state.
The formulation usually given for NFAs seems very close to Formulation 2.1 for discrete feasible planning. Here is a typical NFA formulation [891], which formalizes the ideas depicted in Figure 11.8:

Formulation 11..2 (Nondeterministic Finite Automaton)  

1. A finite state space .
2. A finite alphabet which represents the possible input symbols. Let .
3. A transition function, . For each state and symbol, a set of outgoing edges is specified by indicating the states that are reached.
4. A start state .
5. A set of accept states.

An NFA, similar to a DFA, consumes a string of input symbols. For each input symbol it transitions to a new state until all input symbols have been consumed.
Unlike a DFA, it is non-deterministic in that, for any input symbol, its next state may be any one of several possible states. Thus, in the formal definition, the next state is an element of the power set of states. This element, itself a set, represents some subset of all possible states to be considered at once.

An extension of the NFA is the NFA-lambda (also known as NFA-epsilon or the NFA with epsilon moves), which allows a transformation to a new state without consuming any input symbols. For example, if it is in state 1, with the next input symbol an a, it can move to state 2 without consuming any input symbols, and thus there is an ambiguity: is the system in state 1, or state 2, before consuming the letter a? Because of this ambiguity, it is more convenient to talk of the set of possible states the system may be in. Thus, before consuming letter a, the NFA-epsilon may be in any one of the states out of the set {1,2}. Equivalently, one may imagine that the NFA is in state 1 and 2 'at the same time': and this gives an informal hint of the powerset construction: the DFA equivalent to an NFA is defined as the one that is in the state q={1,2}. Transformations to new states without consuming an input symbol are called lambda transitions or epsilon transitions. They are usually labeled with the Greek letter λ or ε.

The notion of accepting an input is similar to that for the DFA. When the last input symbol is consumed, the NFA accepts if and only if there is some set of transitions that will take it to an accepting state. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state.

 Formal definition

Two similar types of NFAs are commonly defined: the NFA and the NFA with ε-moves. The ordinary is defined as a 5-tuple, (Q, Σ, T, q₀, F), consisting of

• a finite set of states Q
• a finite set of input symbols Σ
• a transition function T : Q × Σ → P(Q).
• an initial (or start) state q₀ ∈ Q
• a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q. The NFA with ε-moves (also sometimes called NFA-epsilon or NFA-lambda) replaces the transition function with one that allows the empty string ε as a possible input, so that one has instead

T : Q × (Σ ∪{ε}) → P(Q).

It can be shown that ordinary NFA and NFA with epsilon moves are equivalent, in that, given either one, one can construct the other, which recognizes the same language.

Markov Chains

A Markov chain, named for Andrey Markov, is a mathematical system that transits from one state to another (out of a finite or countable number of possible states) in a chainlike manner. It is a random process endowed with the Markov property: that the next state depends only on the current state and not on the past. Markov chains have many applications as statistical models of real-world processes.

 A Markov chain is a discrete (discrete-time) random process with the Markov property. Often, the term "Markov chain" is used to mean a Markov process which has a discrete (finite or countable) state-space. Usually a Markov chain would be defined for a discrete set of times (i.e. a discrete-time Markov chain)^[1] although some authors use the same terminology where "time" can take continuous values.^[2][3] Also see continuous-time Markov process. The use of the term in Markov chain Monte Carlo methodology covers cases where the process is in discrete-time (discrete algorithm steps) with a continuous state space. The following concentrates on the discrete-time discrete-state-space case.

Markov chain is the so-called "drunkard's walk", a random walk on the number line where, at each step, the position may change by +1 or −1 with equal probability. From any position there are two possible transitions, to the next or previous integer. The transition probabilities depend only on the current position, not on the way the position was reached. For example, the transition probabilities from 5 to 4 and 5 to 6 are both 0.5, and all other transition probabilities from 5 are 0. These probabilities are independent of whether the system was previously in 4 or 6.

Another example is the dietary habits of a creature who eats only grapes, cheese or lettuce, and whose dietary habits conform to the following (artificial) rules: it eats exactly once a day; if it ate cheese yesterday, it will not today, and it will eat lettuce or grapes with equal probability; if it ate grapes yesterday, it will eat grapes today with probability 1/10, cheese with probability 4/10 and lettuce with probability 5/10; finally, if it ate lettuce yesterday, it won't eat lettuce again today but will eat grapes with probability 4/10 or cheese with probability 6/10. This creature's eating habits can be modeled with a Markov chain since its choice depends on what it ate yesterday, not additionally on what it ate 2 or 3 (or 4, etc.) days ago. One statistical property one could calculate is the expected percentage of the time the creature will eat grapes over a long period.

A series of independent events—for example, a series of coin flips—does satisfy the formal definition of a Markov chain. However, the theory is usually applied only when the probability distribution of the next step depends non-trivially on the current state.