Deprecated: Caller from MediaWiki\Extension\Math\MathRenderer::readFromDatabase ignored an error originally raised from MathObject::readFromDatabase: [1054] Unknown column 'math_mathml' in 'field list' in /var/www/html/includes/debug/MWDebug.php on line 378
Deprecated: Caller from LCStoreDB::get ignored an error originally raised from MathObject::readFromDatabase: [1054] Unknown column 'math_mathml' in 'field list' in /var/www/html/includes/debug/MWDebug.php on line 378 Main Page: Difference between revisions - formulasearchengine
[[File:Cassini projection SW.jpg|thumb|Cassini projection of the world]]
[[File:Cassini projection squashed SW.JPG|thumb|Cassini projection of the world modeled as a highly oblated ellipsoid with flattening 1:2 (= eccentricy √3/2)]]
The '''Cassini projection''' is a [[map projection]] described by [[César-François Cassini de Thury]] in 1745.<ref>''Flattening the Earth: Two Thousand Years of Map Projections'', John P. Snyder, 1993, pp. 74–76, ISBN 0-226-76747-7.</ref> It is the [[transverse aspect]] of the [[equirectangular projection]], in that the globe is first rotated so the central meridian becomes the "equator", and then the normal equirectangular projection is applied. Considering the earth as a sphere, the projection is composed of these operations:
In [[computer science]], a '''computation history''' is a sequence of steps taken by an [[abstract machine]] in the process of computing its result. Computation histories are frequently used in [[Mathematical proof|proofs]] about the capabilities of certain machines, and particularly about the [[undecidable problem|undecidability]] of various [[formal languages]].
Formally, a computation history is a (normally [[Finite set|finite]]) sequence of '''configurations''' of a formal [[automaton]]. Each configuration fully describes the status of the machine at a particular point. To be valid, certain conditions must hold:
* the first configuration must be a valid initial configuration of the automaton and
* each transition between adjacent configurations must be valid according to the transition rules of the automaton.
In addition, to be '''complete''', a computation history must be finite and
* the final configuration must be a valid terminal configuration of the automaton.
The definitions of "valid initial configuration", "valid transition", and "valid terminal configuration" vary for different kinds of formal machines.
A [[deterministic]] automaton has exactly one computation history for a given initial configuration, though the history may be infinite and therefore incomplete.
where <math>\lambda</math> is the longitude from the central meridian and <math>\phi</math> is the latitude. When programming these equations, the [[inverse tangent]] function used is actually the [[atan2]] function, with the first argument <math>\sin(\phi)</math> and the second <math>\cos(\phi)\cos(\lambda)</math>.
== Finite State Machines ==
In practice, the projection has always been applied to models of the earth as an [[Reference ellipsoid|ellipsoid]], which greatly complicates the mathematical development but is suitable for surveying. Nevertheless the use of the Cassini projection has largely been superseded by the [[Transverse Mercator]] projection, at least with central mapping agencies.
For a [[finite state machine]] <math>M</math>, a configuration is simply
the current state of the machine, together with the remaining input. The first configuration must be the initial state of <math>M</math> and the complete input. A transition from a configuration <math>(S,I)</math> to
a configuration <math>(T,J)</math> is allowed if <math>I=aJ</math> for
some input symbol <math>a</math> and if <math>M</math> has a transition from
<math>S</math> to <math>T</math> on input <math>a</math>. The final
configuration must have the empty string <math>\epsilon</math> as its remaining
input; whether <math>M</math> has accepted or rejected the input depends
on whether the final state is an accepting state. <ref name="MumfordJain2009">{{cite book|author1=Christine L. Mumford|author2=Lakhmi C. Jain|title=Computational Intelligence: Collaboration, Fusion and Emergence|url=http://books.google.com/books?id=eECU8WrC99wC&pg=PA337|accessdate=25 March 2012|year=2009|publisher=Springer|isbn=978-3-642-01798-8|page=337}}</ref>
== Turing Machines ==
==Distortions==
Areas along the central meridian, and at right angles to it, are not distorted. Elsewhere, the distortion is largely in a north-south direction, and varies by the square of the distance from the central meridian. As such, the greater the longitudinal extent of the area, the worse the distortion becomes.
Computation histories are more commonly used in reference to [[Turing machines]]. The configuration of a single-tape Turing machine consists of the contents of the tape, the position of the read/write head on the tape, and the current state of the associated state machine; this is usually written
Due to this, the Cassini projection works best on long, narrow areas, and worst on wide areas.
<math>...0011010101q00110101010...</math>
==References==
{{reflist}}
where <math>q</math> is the current state of the machine, represented in some
way that's distinguishable from the tape language, and where <math>q</math> is
positioned immediately before the position of the read/write head.
Consider a Turing machine <math>M</math> on input <math>w</math>. The first
configuration must be <math>q_0 w_0 w_1 ...</math>, where <math>q_0</math>
is the initial state of the Turing machine. The machine's state in the final
configuration must be either <math>q_a</math> (the accept state) or <math>q_r</math>
(the reject state). A configuration <math>c_{i+1}</math> is a valid successor
to configuration <math>c_i</math> if there's a transition from the state in
<math>c_i</math> to the state in <math>c_{i+1}</math> which manipulates the
tape and moves the read/write head in a way that produces the result in
<math>c_{i+1}</math>.<ref name="Blass2010">{{cite book|author=Andreas Blass|title=Fields of Logic and Computation: Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday|url=http://books.google.com/books?id=HqIRT51n74YC&pg=PA468|accessdate=25 March 2012|date=22 October 2010|publisher=Springer|isbn=978-3-642-15024-1|page=468}}</ref>
=== Decidability results ===
==External links==
* [http://www.radicalcartography.net/?projectionref Table of examples and properties of all common projections], from radicalcartography.net
* [http://webarchive.nationalarchives.gov.uk/20100203170955/ordnancesurvey.co.uk/oswebsite/freefun/geofacts/geo1164.html Ordnance Survey GeoFacts on the Cassini Projection]
Computation histories can be used to show that certain problems for
{{Map Projections}}
[[pushdown automata]] are [[undecidable problem|undecidable]]. This is because the language of
non-accepting computation histories of a Turing machine <math>M</math>
on input <math>w</math> is a [[context-free language]] recognizable by a
non-deterministic pushdown automaton.
We encode a Turing computation history <math>c_0,c_1,...,c_n</math> as the
is the encoding of configuration <math>c_i</math>, as discussed above, and where
every other configuration is written in reverse. Before reading a particular
configuration, the pushdown automaton makes a non-deterministic choice
to either ignore the configuration or read it completely onto the stack.
* If the pushdown automaton decides to ignore the configuration, it simply reads and discards it completely and makes the same choice for the next one.
* If it decides to process the configuration, it pushes it completely onto the stack, then verifies that the next configuration is a valid successor according to the rules of <math>M</math>. Since successive configurations are always written in opposite orders, this can be done by, for each tape symbol in the new configuration, popping off a symbol from the stack and checking if they're the same. Where they disagree, it must be accountable for by a valid transition of <math>M</math>. If, at any point, the automaton decides that the transition is invalid, it immediately enters a special accept state which ignores the rest of the input and accepts at the end.
In addition, the automaton verifies that the first configuration is the correct
initial configuration (if not, it accepts) and that the state of the final
configuration of the history is the accept state (if not, it accepts). Since
a non-deterministic automaton accepts if there's any valid way for it to accept,
the automaton described here will discover if the history is not a valid
accepting history and will accept if so, and reject if not. <ref name="Blum1998">{{cite book|author=Lenore Blum|title=Complexity and real computation|url=http://books.google.com/books?id=zxtrVqUP-AwC&pg=PA31|accessdate=25 March 2012|year=1998|publisher=Springer|isbn=978-0-387-98281-6|page=31}}</ref>
This same trick cannot be used to recognize ''accepting'' computation histories
with an NPDA, since non-determinism could be used to skip past a test that would
otherwise fail. A linear-bounded Turing machine is sufficient to recognize
accepting computation histories.
This result allows us to prove that <math>ALL_{PDA}</math>, the language
of pushdown automata which accept all input, is undecidable. Suppose
we have a decider for it, <math>D</math>. For any Turing machine
<math>M</math> and input <math>w</math>, we can form the pushdown automaton
<math>P</math> which accepts non-accepting computation histories for that
machine. <math>D(P)</math> will accept if and only if there are no
accepting computation histories for <math>M</math> on <math>w</math>; this
would allow us to decide <math>A_{TM}</math>, which we know to be undecidable.
==References==
{{reflist}}
[[Category:Theory of computation]]
{{DEFAULTSORT:Cassini Projection}}
[[Category:Cartographic projections]]
[[pt:Histórico de computação]]
{{Cartography-stub}}
Revision as of 16:08, 15 August 2014
Cassini projection of the worldCassini projection of the world modeled as a highly oblated ellipsoid with flattening 1:2 (= eccentricy √3/2)
The Cassini projection is a map projection described by César-François Cassini de Thury in 1745.[1] It is the transverse aspect of the equirectangular projection, in that the globe is first rotated so the central meridian becomes the "equator", and then the normal equirectangular projection is applied. Considering the earth as a sphere, the projection is composed of these operations:
where is the longitude from the central meridian and is the latitude. When programming these equations, the inverse tangent function used is actually the atan2 function, with the first argument and the second .
In practice, the projection has always been applied to models of the earth as an ellipsoid, which greatly complicates the mathematical development but is suitable for surveying. Nevertheless the use of the Cassini projection has largely been superseded by the Transverse Mercator projection, at least with central mapping agencies.
Distortions
Areas along the central meridian, and at right angles to it, are not distorted. Elsewhere, the distortion is largely in a north-south direction, and varies by the square of the distance from the central meridian. As such, the greater the longitudinal extent of the area, the worse the distortion becomes.
Due to this, the Cassini projection works best on long, narrow areas, and worst on wide areas.
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
