Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
No edit summary
No edit summary
Line 1: Line 1:
{{about|zero objects or trivial objects in algebraic structures|zero object in a category|Initial and terminal objects|trivial representation|trivial representation}}
<!-- {{redirect|{0}|0 (disambiguation)}} -->
{{Merge from|trivial group|discuss=Talk:Zero object (algebra)#Zero object (algebra)|date=February 2012}}
{{refimprove|date=February 2012}}
[[Image:Terminal and initial object.svg|thumb|right|[[Morphism]]s to and from the zero object]]
In [[algebra]], the '''zero object''' of a given [[algebraic structure]] is, in the sense explained below, the simplest object of such structure. As a [[set (mathematics)|set]] it is a [[singleton (mathematics)|singleton]], and also has a [[trivial group|trivial]] structure of [[abelian group]]. Aforementioned group structure usually identified as the [[addition]], and the only element is called [[zero]]&nbsp;0, so the object itself is denoted as {{math|{0}{{void}}}}. One often refers to ''the'' trivial object (of a specified [[category (mathematics)|category]]) since every trivial object is [[isomorphism|isomorphic]] to any other (under a unique isomorphism).


Instances of the zero object include, but are not limited to the following:
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]].
* As a [[group (mathematics)|group]], the '''trivial group'''.
* As a [[ring (mathematics)|ring]], the '''trivial ring'''.
* As a [[module (mathematics)|module]] (over a [[ring (algebra)|ring]]&nbsp;{{mvar|R}}), the '''zero module'''. The term ''trivial module'' is also used, although it is ambiguous.
* As a [[vector space]] (over a [[field (mathematics)|field]]&nbsp;{{mvar|R}}), the '''zero vector space''', '''zero-dimensional vector space'''  or just '''zero space'''; see [[#Vector space|below]].
* As an [[algebra over a field]] or [[algebra over a ring]], the '''trivial algebra'''.
These objects are described jointly not only based on the common singleton and trivial group structure, but also because of [[#Properties|shared category-theoretical properties]].


{{anchor|Module}}In the last three cases the [[scalar multiplication]] by an element of the base ring (or field) is defined as:
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:
: {{math|1= κ0 = 0 }}, where {{math|κ ∈ ''R''}}.
* the first configuration must be a valid initial configuration of the automaton and
The most general of them, the zero module, is a [[finitely-generated module]] with an [[empty set|empty]] generating set.  
* 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.


{{anchor|Algebra}}{{anchor|Ring}}For structures requiring the multiplication structure inside the zero object, such as the trivial ring, there is only one possible, {{math|1=0 × 0 = 0}}, because there are no non-zero elements. This structure is [[associativity|associative]] and [[commutative]]. A ring {{mvar|R}} which has both an additive and multiplicative identity is trivial if and only if {{nowrap|1=1 = 0}}, since this equality implies that for all {{mvar|r}} within {{mvar|R}},
A [[deterministic]] automaton has exactly one computation history for a given initial configuration, though the history may be infinite and therefore incomplete.
:<math>r = r \times 1 = r \times 0 = 0. \,</math>
In this case it is possible to define [[division by zero]], since the single element is its own multiplicative inverse. Some properties of {0} depend on exact definition of the multiplicative identity; see the section [[#Unital structures|Unital structures]] below.


Any '''trivial algebra''' is also a trivial ring. A trivial [[algebra over a field]] is simultaneously a zero vector space considered [[#Vector space|below]]. Over a [[commutative ring]], a trivial [[algebra over a ring|algebra]] is simultaneously a zero module.
== Finite State Machines ==
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>


The trivial ring is an example of a [[zero ring]]. Likewise, a trivial algebra is an example of a [[Algebra over a field#Zero algebras|zero algebra]].
== Turing Machines ==


; {{visible anchor|Vector space}}
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
The zero-dimensional vector space is an especially ubiquitous example of a zero object, a [[vector space]] over a field with an empty [[basis (linear algebra)|basis]]. It therefore has [[dimension (mathematics)|dimension]] zero. It is also a trivial group over [[addition]], and a ''trivial module'' [[#Module|mentioned above]].


== Properties ==<!-- linked from the lede -->
<math>...0011010101q00110101010...</math>
{| table align=right valign=center width="32em" style="margin-left:2em"
|- align=center
| bgcolor=#66FFFF align=right | 2<span style="font-size:160%">↕</span>&nbsp;
| <math>\begin{bmatrix}0 \\ 0\end{bmatrix}</math>
| style="font-size:200%" | =
| <math>\begin{bmatrix} \,\\ \,\end{bmatrix}</math>
| <span style="font-size:40%; font-weight:900">[</span> <span style="font-size:40%; font-weight:900">]</span>
| bgcolor=#66FFFF align=left | &nbsp;‹0
|- bgcolor=#66FFFF align=center
|
| ↔<br/>1
|
| ^<br/>0
| ↔<br/>1
|
|-
| colspan=6 style="font-size:75%" | Element of the zero space, written as empty [[column vector]] (rightmost one), <br/> is multiplied by 2×0 [[empty matrix]] to obtain 2-dimensional zero vector </br> (leftmost). Rules of [[matrix multiplication]] are respected.
|}
The trivial ring, zero module and zero vector space are [[zero object]]s of the corresponding [[category (mathematics)|categories]], namely <span class="nounderlines">[[Category of pseudo-rings|'''Rng''']], [[Category of modules|{{mvar|R}}-'''Mod''']] and [[Category of vector spaces|'''Vect'''<sub>{{mvar|R}}</sub>]]</span>.


The zero object, by definition, must be a terminal object, which means that a [[morphism]]&nbsp;{{math|''A'' → {0}{{void}}}} must exist and be unique for an arbitrary object&nbsp;{{mvar|A}}. This morphism maps any element of&nbsp;{{mvar|A}} to&nbsp;{{math|0}}.
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.


The zero object, also by definition, must be an initial object, which means that a morphism&nbsp;{{math|{0} → ''A''}} must exist and be unique for an arbitrary object&nbsp;{{mvar|A}}. This morphism maps {{math|0}}, the only element of&nbsp;{{math|{0}{{void}}}}, to the zero element&nbsp;{{math|0 ∈ ''A''}}, called the [[zero vector]] in vector spaces. This map is a [[monomorphism]], and hence its image is isomorphic to&nbsp;{0}. For modules and vector spaces, this [[subset]]&nbsp;{{math|{0} ⊂ ''A''}} is the only empty-generated [[submodule]] (or 0-dimensional [[linear subspace]]) in each module (or vector space)&nbsp;{{mvar|A}}.
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>


=== Unital structures ===<!-- linked from the lede -->
=== Decidability results ===
The {0} object is a [[terminal object]] of any algebraic structure where it exists, like it was described for examples above. But its existence and, if it exists, the property to be an [[initial object]] (and hence, a ''zero object'' in the [[category theory|category-theoretical]] sense) depend on exact definition of the [[multiplicative identity]]&nbsp;1 in a specified structure.


If the definition of&nbsp;1 requires that {{math|1 ≠ 0}}, then the {0} object cannot exist because it may contain only one element. In particular, the zero ring is not a [[field (mathematics)|field]]. If mathematicians sometimes talk about a [[field with one element]], this abstract and somewhat mysterious mathematical object is not a field.
Computation histories can be used to show that certain problems for
[[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.


In categories where the multiplicative identity must be preserved by morphisms, but can equal to zero, the {0} object can exist. But not as initial object because identity-preserving morphisms from {0} to any object where {{math|1 ≠ 0}} do not exist. For example, in the [[category of rings]] '''Ring''' the ring of [[integer]]s&nbsp;'''Z''' is the initial object, not&nbsp;{0}.
We encode a Turing computation history <math>c_0,c_1,...,c_n</math> as the
string <math>C_0 \# C^r_1 \# C_2 \# C^r_3 \# ... \# C_n</math>, where <math>C_i</math>
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 an algebraic structure requires the multiplicative identity, but does not require neither its preserving by morphisms nor {{math|1 ≠ 0}}, then zero morphisms exist and the situation is not different from non-unital structures considered in the previous section.
* 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.


== Notation ==
In addition, the automaton verifies that the first configuration is the correct
Zero vector spaces and zero modules are usually denoted by 0 (instead of {0}). This is always the case when they occur in an [[exact sequence]].
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>


== See also ==
This same trick cannot be used to recognize ''accepting'' computation histories
* [[Triviality (mathematics)]]
with an NPDA, since non-determinism could be used to skip past a test that would
* [[Examples of vector spaces]]
otherwise fail.  A linear-bounded Turing machine is sufficient to recognize
* [[Field with one element]]
accepting computation histories.
* [[Zero element (disambiguation)]]
* [[List of zero terms]]


== External links ==
This result allows us to prove that <math>ALL_{PDA}</math>, the language
* {{cite book | author=David Sharpe | title=Rings and factorization | publisher=[[Cambridge University Press]] | year=1987 | isbn=0-521-33718-6 | page=10 }}
of pushdown automata which accept all input, is undecidable.  Suppose
* {{MathWorld|title=Trivial Module|id=TrivialModule|author=[[Margherita Barile|Barile, Margherita]]}}
we have a decider for it, <math>D</math>.  For any Turing machine
* {{MathWorld|title=Zero Module|id=ZeroModule|author=Barile, Margherita}}
<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:Ring theory|0]]
[[Category:Theory of computation]]
[[Category:Linear algebra|0]]
[[Category:Zero|Object]]
[[Category:Objects (category theory)|0]]


<!-- these interwiki are actually of [[trivial ring]] -->
[[pt:Histórico de computação]]
[[ca:Anell trivial]]
[[de:Nullring]]
[[es:Anillo trivial]]
[[fr:Anneau nul]]
[[nl:Triviale ring]]
[[pl:Pierścień trywialny]]

Revision as of 14:54, 15 August 2014

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 proofs about the capabilities of certain machines, and particularly about the undecidability of various formal languages.

Formally, a computation history is a (normally 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.

Finite State Machines

For a finite state machine M, a configuration is simply the current state of the machine, together with the remaining input. The first configuration must be the initial state of M and the complete input. A transition from a configuration (S,I) to a configuration (T,J) is allowed if I=aJ for some input symbol a and if M has a transition from S to T on input a. The final configuration must have the empty string ϵ as its remaining input; whether M has accepted or rejected the input depends on whether the final state is an accepting state. [1]

Turing Machines

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

...0011010101q00110101010...

where q is the current state of the machine, represented in some way that's distinguishable from the tape language, and where q is positioned immediately before the position of the read/write head.

Consider a Turing machine M on input w. The first configuration must be q0w0w1..., where q0 is the initial state of the Turing machine. The machine's state in the final configuration must be either qa (the accept state) or qr (the reject state). A configuration ci+1 is a valid successor to configuration ci if there's a transition from the state in ci to the state in ci+1 which manipulates the tape and moves the read/write head in a way that produces the result in ci+1.[2]

Decidability results

Computation histories can be used to show that certain problems for pushdown automata are undecidable. This is because the language of non-accepting computation histories of a Turing machine M on input w is a context-free language recognizable by a non-deterministic pushdown automaton.

We encode a Turing computation history c0,c1,...,cn as the string C0#C1r#C2#C3r#...#Cn, where Ci is the encoding of configuration ci, 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 M. 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 M. 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. [3]

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 ALLPDA, the language of pushdown automata which accept all input, is undecidable. Suppose we have a decider for it, D. For any Turing machine M and input w, we can form the pushdown automaton P which accepts non-accepting computation histories for that machine. D(P) will accept if and only if there are no accepting computation histories for M on w; this would allow us to decide ATM, which we know to be undecidable.

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.

pt:Histórico de computação

  1. ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  2. ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  3. ↑ 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=63918"