Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
No edit summary
No edit summary
 
(281 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


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]].
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


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:
Registered users will be able to choose between the following three rendering modes:
* 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.
'''MathML'''
:<math forcemathmode="mathml">E=mc^2</math>


== Finite State Machines ==
<!--'''PNG''' (currently default in production)
For a [[finite state machine]] <math>M</math>, a configuration is simply
:<math forcemathmode="png">E=mc^2</math>
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 ==
'''source'''
:<math forcemathmode="source">E=mc^2</math> -->


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
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


<math>...0011010101q00110101010...</math>
==Demos==


where <math>q</math> is the current state of the machine, represented in some
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:
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 ===
* accessibility:
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


Computation histories can be used to show that certain problems for
==Test pages ==
[[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
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
string <math>C_0 \# C^r_1 \# C_2 \# C^r_3 \# ... \# C_n</math>, where <math>C_i</math>
*[[Displaystyle]]
is the encoding of configuration <math>c_i</math>, as discussed above, and where
*[[MathAxisAlignment]]
every other configuration is written in reverse.  Before reading a particular
*[[Styling]]
configuration, the pushdown automaton makes a non-deterministic choice
*[[Linebreaking]]
to either ignore the configuration or read it completely onto the stack.
*[[Unique Ids]]
*[[Help:Formula]]


* 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.
*[[Inputtypes|Inputtypes (private Wikis only)]]
* 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.
*[[Url2Image|Url2Image (private Wikis only)]]
 
==Bug reporting==
In addition, the automaton verifies that the first configuration is the correct
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
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]]
 
[[pt:Histórico de computação]]

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"