text:
User talk:AmenRa~enwikibooks

Welcome
Hello, and welcome to Wikibooks!

Here are some tips to help you get started:
 * To learn the wiki-markup-language syntax, see Help:Editing.
 * You should sign your name on Talk and vote pages using four tildes, like this: ~~~~
 * There is a box at the top of the edit window that will insert this, too; it looks like part of a signature.
 * Remember to conduct any editing experiments in the sandbox.
 * You can tell the community something about yourself in your userpage.
 * You can get to this page by clicking the tab at the top of the page labeled with your registered username.
 * If you are a Wikipedian, see Wikibooks for Wikipedians for a primer on how things work here (it's a little different).
 * If you want to base your work here on materials from Wikipedia, please use WB:RFI (requests for importation) to bring the material over in compliance with the GFDL.
 * If you're an instructor and plan on using Wikibooks for a class project, see Guidelines for class projects
 * Please say hello at the Staff Lounge with any questions or ideas.
 * Eventually, you might want to read the Manual of Style and Policies and Guidelines.
 * Please take a look at Naming policy before starting a new book.
 * Remember to maintain a Neutral point of view.
 * Explore, be bold in editing pages, and have fun!

You will find more resources in Community Portal. If you want to ask a question, visit the Study help desk, the Staff lounge, IRC channel or ask me personally on my talk page. For site news, see the Bulletin board. It might be a good idea to add this page to your "watchlist" so that you can see when any new information is posted there. You can do that by clicking the tab labeled "watch" at the top of the page.

Good luck! --Derbeth talk 19:19, 9 May 2007 (UTC)

Image:Al T9083.gif
Please provide detailed information about source of this image. --Derbeth talk 19:19, 9 May 2007 (UTC)
 * Please give URL link to original file. --Derbeth talk 10:56, 13 May 2007 (UTC)

Interwiki links
Just so you know, you can make links to Wikipedia using the Whatever_you_want_to_call_it syntax, for example to link to the "life" article:

Life is good yields:

Life is good

Hope this helps! Mattb112885 (talk) 23:46, 11 May 2007 (UTC)

Copyrights
Hi, it appears that most of the text on the 2C-H module is copied directly from this site which has a license that is incompatible with Wikibooks (Wikibooks requires that all text be under a GNU-compatible license, meaning the text can be reused for any purpose as long as attribution is given). I am not sure if it would be appropriate to use it in this manner, so I would request that though you may use the site as a reference, you refrain from verbatim copying from copyrighted sources. Thank you for your time. Mattb112885 (talk) 01:14, 12 May 2007 (UTC)

Image:Addition funnel.jpg
What is the source of this image (book title, website URL)? --Derbeth talk 09:34, 16 May 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called AmenRa. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name AmenRa~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 22:57, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 04:31, 19 April 2015 (UTC)

title: User talk:AmenRa~enwikibooks


text:
C Sharp Programming/Keywords/do

The keyword identifies the beginning of a  loop.

/Keywords

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: C Sharp Programming/Keywords/do


text:
C Sharp Programming/Keywords/yield

The keyword returns the next value from an iterator or ends an iteration.

/Keywords

title: C Sharp Programming/Keywords/yield


text:
Computability and Complexity

= Table of Contents =

This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is Computer Science and Math students with some background in programming, data structures, and discrete math, such as a sophomore in a Computer Science program.

 * Introduction
 * Formal Languages
 * Chomsky Hierarchy
 * Regular Languages      - sample DFA inputs
 * Context Free Languages    - sample PDA inputs
 * Context Sensitive Languages - sample LBA inputs
 * Unrestricted Languages    - sample TM inputs
 * Other Language Classes
 * Counting Languages - sample CA inputs
 * Computability
 * Decidability
 * Reducibility
 * Complexity
 * Time Complexity
 * P
 * P-Complete
 * NP
 * NP-Complete
 * Space Complexity
 * L
 * NL
 * NL-Complete
 * PSPACE
 * PSPACE-Complete
 * References and Further Reading

title: Computability and Complexity


text:
Computability and Complexity/Introduction

This book is intended as a guide to the topics of computability and complexity in theoretical computer science for the mid-level undergraduate student. It assumes a working knowledge of discrete math, and uses Perl for all example programs.

The emphasis of the work so far has been on formal languages, particularly the Chomsky hierarchy, and on the machines that correspond to that hierarchy. The major areas that need filling out are the section on reducibility, and the sections on time and space complexity. Adding more language classes outside the Chomsky hierarchy would also improve the formal languages section, and adding information about the pumping lemmas to the sections on Regular Languages and the Context Free Languages would improve those sections.

Table of Contents

References and Further Reading

Previous | Next


text:
Computability and Complexity/Formal Languages

= Formal Languages = Central to ideas of complexity in computer science is the concept of formal languages. A formal language is a collection of words, which are strings of finite length drawn from a finite alphabet of symbols usually called $$\Sigma$$. We study the computational complexity of machines that define a particular language by either accepting or rejecting every possible word in its alphabet.

While each word in a language must be finite, a language may contain words of arbitrary length, and thus may contain an infinite number of words. An example of such a language is the collection of all strings drawn from the alphabet $$\Sigma=\{a,b\}$$ which contain a number of a followed by an equal number of b. This language thus contains any string of the form $$a^nb^n$$, where $$a^n$$ is the symbol a repeated n times. Since n can be any positive integer, there must be an infinite number of words in this language.

Many formal languages have associated with them a generative grammar, which is a set of replacement rules containing three types of symbols: ε, which signifies the empty string (a string of length 0), non-terminal symbols, which are symbols not in the alphabet of the language, and terminal symbols, which are in the alphabet of the language. By convention, non-terminal symbols are usually capital letters, while terminal symbols (and thus the alphabet of the associated formal language) are usually lower-case letters. The grammars also include a non-terminal symbol called the start symbol, which is what the replacement rules assume is present before any replacements happen. By making choices about which replacement rule to apply when, the start symbol can be converted into any word in the language associated with that grammar and into no other words, which is why the grammar is said to generate the language. How these replacement rules can be formed depends on the language class involved, and each set of restrictions on the grammar creates a class of generative grammars. Not every class of formal languages has a class of generative grammars associated with it.

The other object often associated with language classes is recognizing machines. How these machines operate and what their restrictions are depends on the language class they correspond to, but a machine is said to recognize a language if, when given any word in that language as an input, the machine always "accepts" the word, and never "accepts" a word that is not in the language. Not all formal language classes have a type of recognizing machine associated with them, but most languages studied by computer scientists do.

There are a number of classes of different languages, each based on the complexity of the languages it contains. The best known language classes are the four classes of the /Chomsky Hierarchy/, which were defined by Noam Chomsky in his 1959 paper "On Certain Formal Properties of Grammars" 1. Information on other language classes can be found in the chapter /Other Language Classes/.

In summary:
 * An alphabet is a finite collection of symbols.
 * A word is a string of finite length whose symbols are drawn from an alphabet.
 * A formal language is a collection of words.
 * A generative grammar is a set of replacement rules that allow you to create any word in the language (and no other words) from a start symbol.
 * A recognizing machine is a machine that "accepts" any word in the language (and no other words).
 * A language class is a set of languages that are of similar complexity, so they have similar types of generative grammar and similar types of recognizing machines.

Previous | Next


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy

= Chomsky Hierarchy =

The Chomsky hierarchy is a collection of four classes of formal languages, each of which is a proper subset of the classes above it, and each of which corresponds to both a generating grammar and to a recognizing machine. This hierarchy developed primarily from the works of Noam Chomsky and Marcel-Paul Schutzenberger in the late 1950s on mechanistic linguistics and formal languages. The various levels of the hierarchy have proven useful in both theoretical and applied computer science, as they connect to Alan Turing's work on algorithms and computability, and in compiler design.

Each level of this hierarchy consists of a class of formal languages, a class of generative grammars, each of which produces a language in the associated class, and a class of machines, each of which recognizes a language in the associated class. At each level of the hierarchy, the rules for the generative grammar become more restrictive, making each class of languages a subset of the classes above it. Those four classes, from most restrictive to least restrictive, are:
 * /Regular Languages/
 * /Context Free Languages/
 * /Context Sensitive Languages/
 * /Unrestricted Languages/

Previous | Next


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/Regular Languages

= Regular Languages =

Regular languages are the most restricted, and the simplest, languages in the Chomsky Hierarchy. Languages in this class are usually described like mathematical sets, with a description in curly brackets. Any word that matches that description is part of the language, and any word that doesn't match the description isn't part of the language.

Informally, the class of regular languages is those languages which can be described by characters from its alphabet with concatenation, parentheses, the ∪ (or) operator, and the * operator. An example would be $$\{(b \cup (ab))*\}$$, the language containing any number of as and bs, where every a is followed by a b.

It should be noted that any finite language, which is a language comprised of some finite sequence of words $$w_1, w_2, \ldots, w_n$$, can be written as $$\{w_1 \cup w_2 \cup \ldots \cup w_n\}$$. As a result, every finite language is regular. The converse of this, however, is not true. The example language given earlier, $$\{(b \cup (ab))*\}$$, contains an infinite number of words, and is regular.

An alternative, though equivalent, definition of the regular languages is those languages which can be generated by a regular grammar. A regular grammar is a set of rules which, starting from an initial symbol, replace "non-terminal symbols" (symbols which are not in the alphabet of the language) with "terminal symbols" (symbols which are in the alphabet of the language) through replacement rules that replace each non-terminal symbol with either a terminal symbol, a terminal symbol followed by a non-terminal symbol, or ε (the empty string). As an example, the language $$\{(b \cup (ab))*\}$$ above can be described by the following grammar (let S be the starting symbol): Note that by making different choices about which rules to apply when, this grammar can produce, from a starting string of "S", the empty string or a string of as and bs with every a followed by a b. This is exactly the same as the words matching the set notation above, making the languages produced by the two methods identical.
 * S -> ε
 * S -> aB
 * S -> b
 * S -> bA
 * A -> aB
 * A -> b
 * A -> bA
 * B -> bA
 * B -> b

Finite Automata
Finite automata are machines that consist of a finite number of states, and transition between those states based only on the current state and a character input. When the input has all been consumed, the machine either "accepts" or "rejects" the string of inputs, based on the final state of the machine. These machines happen to correspond exactly with regular languages, with the set of strings accepted by any finite automaton being a regular language, and with every regular language having a machine that accepts all and only strings from that language. For this reason we say that the class of regular languages is equivalent to the class of languages recognized by finite automata.

DFAs & NFAs
There are two types of finite automata, deterministic and non-deterministic. A deterministic finite automaton, or DFA, makes one transition per character in the input, and contains a transition from each state for each character in the alphabet.

A non-deterministic finite automaton, or NFA, can consume either one or no characters per transition, does not need a transition for each character from each state, and can have more than one possible transition for a specific input and a specific state. These properties allow the NFA to contain computation branches. If any computation branch generated by a string accepts, the machine accepts that string, and only rejects if no branch accepts. Since DFAs are more restrictive than NFAs, every DFA is also an NFA, and any NFA can be converted into a DFA, so the set of languages recognized by all NFAs and DFAs is the same, and the two machines are equivalent.

For either type, the automaton can be specified completely by its set of states, its alphabet, the set of transitions, the start state, and the accepting states.

Limitations
Not all languages are regular. Take the language $$\{a^n b^n|n \ge 0\}$$, whose words contain some number of as followed by an equal number of bs. The only memory that a finite automaton has is its current state, so it can count a number of as no larger than the number of states it possesses. Since the language contains all words of this type, the words can have an arbitrarily large number of as, so for any machine, there must be some strings whose number of as it cannot store. If it cannot store the number of as, then it cannot compare the number of as and bs, and so cannot verify that any string is a member of the language. As a result, there is no finite automaton that recognizes this language, and so it cannot be a regular language.

Examples
The code below is a sample DFA emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.

The syntax is: progname.pl DFAFile inputFile, where DFAFile is a text file containing the DFA instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of DFA instructions, can be found under ../sample DFA inputs/

Previous | Next


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample DFA inputs

= Sample DFA inputs =

These examples are for use with the perl DFA emulator provided at the bottom of ../Regular Languages/. That page also contains a description of what a DFA is and how it works.

The specifications for a machine that accepts all strings ending in b: :States: q1 q2 q3 :Start State: q1 :Accept States: q3 :alphabet: a b :rules: q1 a q2 q1 b q3 q2 a q2 q2 b q3 q3 a q2 q3 b q3

Some sample words:

this accepts: b a b a b this rejects: a a b b a a b a

(the empty string)

back


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/Context Free Languages

= Context Free Languages =

Context free languages are the second most restricted class of languages in the Chomsky Hierarchy. Languages in this class can be described by a set of generation rules using 'non-terminal' symbols and 'terminal symbols', where the terminal symbols are the alphabet of the language. These rules replace non-terminal symbols with strings of terminals or non-terminals, or with an empty string. It is common practice to use capital letters for the non-terminal symbols, and lower-case letters for the symbols in the alphabet (and thus for the terminal symbols). This set of replacement rules is called a context-free grammar. A language is context free if there is a context-free grammar which generates every string in the language (and no other strings) from a starting non-terminal symbol.

As an example, consider the following grammar: From the starting symbol S, this grammar can generate either the empty string or a word composed of any number of as followed by an equal number of bs. You may recall from the section on ../Regular Languages/ that this language, which can also be written as $$\{a^n b^n|n \ge 0\}$$, is not part of the class of regular languages, but we now see that it is context-free.
 * S -> ε (ε here stands for the empty string)
 * S -> A
 * A -> aAb
 * A -> ab

Note, in the example, that the grammar provides a choice with what rule to apply to both S and A non-terminals. It is these choices that allow the grammar to generate all the strings in a language, and not just a single string.

Pushdown Automata
The class of context free languages is the same as the class of languages recognized by machines called pushdown automata. A pushdown automaton (PDA) is a non-deterministic machine comprised of a finite number of states with transitions between them, much like an NFA (see ../Regular Languages/), but with the addition of a stack of unlimited size. As part of its transitions, the machine can pop the top item off of the stack and use its contents as part of its transition, and can also push a new item onto the stack. Its transitions can be written as {A,x,y} -> {B,z}, where A and B are the from and to states, x is the next input character, y is what is popped off the stack, and z is what is placed on the stack. Any of x, y, or z can be ε, meaning that nothing is placed or consumed as part of that transition.

Abilties
The addition of the stack provides a functionally limited but arbitrarily large amount of memory to the machine, enabling it to recognize more complex languages than finite automata. As above, the language $$\{a^nb^n|n \ge 0\}$$ is a context-free language, and so there is a PDA which recognizes it. It can do this by adding an item to the stack for each a in the string, thus storing a count of them, and removing an item from the stack for each b. If the number of as and bs is the same, the stack will empty when there are no more bs, and so the two numbers can be effectively compared. For a more detailed example of a machine to recognize this language, see the sample machine below.

If a PDA simply doesn't use the stack, it is the same as an NFA and thus equivalent to a DFA, so any languages recognized by a finite automaton can be recognized by a PDA as well. Because of this, and because there are non-regular languages which are context-free, the class of regular languages is a proper subset of the class of context-free languages.

Limitations
As with the regular languages, there are many languages which are not context-free. The stack on the PDA, while it provides infinite storage capacity, is still a stack, and so only the last element placed on it can be accessed at any given time. Accessing earlier elements requires removing and thus losing the later elements, since there is no other stack on which to place them. The PDA is also limited in that it must consume the input characters in the order in which they are received, and cannot access them again, except by placing them on the stack.

These limitations make it impossible for a PDA to recognize the language $$\{a^nb^nc^n|n \ge 0\}$$. By using the stack, a PDA can count the number of as, and compare them to the number of bs, but in doing so, it must consume its record of the as, so the cs cannot be compared in the same way. The machine cannot create a record of the bs to compare with the cs without obscuring the count of the as, so that method is equally unsuccessful. In short, the lack of any sort of random or direct access to the memory of the PDA prevents it from recognizing this and many other languages, and since no PDA can recognize them, they cannot be context-free languages.

Examples
The code below is a sample PDA emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.

The syntax is: progname.pl PDAFile inputFile, where PDAFile is a text file containing the TM instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of PDA instructions for a machine to recognize $$\{a^nb^n|n \ge 0\}$$, can be found under ../sample PDA inputs/

Previous | Next


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample PDA inputs

= Sample PDA Inputs =

These examples are for use with the perl PDA emulator provided at the bottom of ../Context Free Languages/. That page also contains a description of what a PDA is and how it works.

The specification for a machine that accepts any string of the form $$\{a^{n}b^{n}|n \ge 0\}$$: :States: q1 q2 q3 q4 :Start State: q1 :Accept States: q4 :alphabet: a b :stack alphabet: $ a :rules: q1 e e q4 $ q1 e e q2 $ q2 b a q3 e q2 a e q2 a q3 b a q3 e q3 e $ q4 e

Some sample inputs: these accept: a a b b

(the empty string)

a a a a a b b b b b

these reject: a a a b b b b b

a a a b b

A machine that accepts any string that consists of at least one 'a' followed by at least as many 'b's: :States: q1 q2 q3 q4 :Start State: q1 :Accept States: q4 :alphabet: a b :stack alphabet: $ a :rules: q3 b e q3 e q3 b a q3 e q2 b a q3 e q2 a e q2 a q1 e e q2 $ q3 e $ q4 e

Some sample inputs: these accept: a b

a a a b b b b b b b

these reject:

(the empty string)

a a a b b

back


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/Context Sensitive Languages

= Context Sensitive Languages =

Context sensitive languages are those languages whose strings can be generated by a context sensitive grammar. This type of grammar is similar in form to a context free grammar (see ../Context Free Languages/), but instead of rules of the form A -> X, where A is a non-terminal symbol and X is a string of terminals and non-terminals, a context sensitive grammar contains rules of the form X -> Y, where X and Y are strings of terminals and non-terminals, with the constraint that Y be at least as long as X.  There is an exception to this rule, that if S is the starting symbol, and S never appears on the right side of a transition, then the transition S -> ε is allowed. This makes it possible for a grammar to generate the empty string.

An example of such a grammar is: This grammar generates the language $$\{a^nb^nc^n|n \ge 0\}$$, a language which is not context free.
 * S -> ε|aAbc|abc
 * A -> aAbC|abC
 * Cb -> bC
 * Cc -> cc

An alternative definition for a context sensitive grammar is a grammar where each of transitions has the form YAZ -> YXZ, where A is a non-terminal, and X, Y and Z are all strings of terminals and non-terminals (Y and Z may empty). Because Y and Z remain unchanged, this fills the same function as a transition A -> X, but can use the context of A as a requirement for the transition. In 1, Noam Chomsky shows that these two definitions are equivalent, and produce the same languages.

Any context free grammar is also a context sensitive grammar under the second definition which only uses empty contexts, so the set of context free languages is a subset of the set of context sensitive languages. Since, in the example above, a context sensitive grammar can produce the language $$\{a^{n}b^{n}c^{n}|n \ge 0\}$$ while a PDA cannot, the context free languages must be a proper subset of the context sensitive languages.

Linear Bounded Automata
The class of context sensitive languages is equivalent to the class of languages that can be recognized by linear bounded automata. A linear bounded automaton (LBA) is a deterministic machine based on a state, a "tape" that contains the input string, and a read/write head that moves left and right along the tape. The machine compares its current state and the symbol on the tape at the head's position with a finite number of rules to determine its next state, what symbol to write on the tape, and which direction (left/right) to move the tape head in. Similarly to both finite automata and pushdown automata, linear bounded automata accept or reject an input based on whether they halt in an accept state or not. An LBA halts when there are no rules for its current combination of state and character being read.

The only other restriction on an LBA is that the tape must be finite, with a size linearly derived from the size of the input string. For example, if a particular machine uses tapes 2*s+5 long, where s is the size of the input, then when processing a string of size 10, it would have a tape of length 25.

Abilities
This design gives the LBA a great deal of computational freedom, and so it can recognize any languages whose space requirements for string recognition grow linearly. One example is the language $$\{a^{n}b^{n}c^{n}d^{n}|n \ge 0\}$$. This language can be recognized in space s+1, meaning that it only requires the section of the tape it was written on, plus a single blank character at the end. This is because unlike a PDA or DFA, an LBA need not deal with the input in sequence - it can (and does in the sample machine available below) mark off the characters in sets, first an 'a', then a 'b', then a 'c', then a 'd', and repeat. It will not accept if it does not exhaust all character types on the same run.

This language cannot be recognized by DFAs and PDAs, because they would have to count and store the number of 'a's as they went by. A DFA could only remember a number of 'a's equal to or fewer than its number of states, and so could not check the number of 'b's in an arbitrarily long string. A PDA could store the number of 'a's on the stack, but would necessarily destroy that information when comparing them to the 'b's, and thus could not compare it to the number of 'c's.

Looping
Note that while it is possible for an LBA to enter an infinite loop, since there is only a finite tape, a finite number of symbols to put on it, and a finite number of states it can be in, the total number of conditions for a given machine and input is finite. That means that any infinite loop must, within a finite number of steps, return to a set of conditions it has already encountered. Also, since LBAs are deterministic, a machine that repeats its set of conditions will continue to repeat the loop it has just traversed indefinitely. These two statements show that an LBA is caught in an infinite loop (and thus will never accept or reject) if and only if it repeats its total conditions (including state, head position, and tape contents). Since $$S \cdot T \cdot A^T$$ is the total number of possible conditions, where S is the number of states, T is the size of the tape, and A is the size of the alphabet, any machine that runs through more than S*T*A^T steps must repeat a set of conditions, and thus be in an infinite loop. While this number may be quite large, it provides a definite, finite-time method of determining whether a given LBA will loop on a given input. The similar but more advanced Turing Machine (see ../Unrestricted Languages/) will have no such method.

Examples
The code below is a sample LBA emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.

The syntax is: progname.pl LBAFile inputFile, where LBAFile is a text file containing the LBA instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of LBA instructions for a machine to recognize $$\{a^nb^nc^nd^n|n \ge 0\}$$, can be found under ../sample LBA inputs/

use Text::ParseWords; use strict; use warnings; my (@tape, $tapeIndex, $tapeMax, %accepts, %alphabet, @rules); my $lbaFile = $ARGV[0]; my $input = $ARGV[1]; my $machine = readLBA($lbaFile); @rules = @{$machine->{rules}}; %accepts = %{$machine->{accepts}}; ($tapeMax, @tape) = readInput($input, $machine->{alphabet}, $machine->{tapeBound}); my $changed = 1; my $state = $machine->{startState}; $tapeIndex = 0; while($changed) {   # Unless it changes while going through the rules, the machine will terminate. $changed = 0; # The current tape is printed, with the symbol under the head highlighted. print "@tape[0..$tapeIndex-1]<".$tape[$tapeIndex].">@tape[$tapeIndex+1..@tape-1]\n"; # The current state of the machine is printed. print "$state\n"; # A new state is calculated by checking conditions against the list of rules for my $rNum (0..@rules-1) {       # Checks the current state and tape symbol against the rule being examined if (($rules[$rNum][0] eq $state) and            ($rules[$rNum][1] eq $tape[$tapeIndex])) {           # The state transition is printed. # Set the new state, $state = $rules[$rNum][2]; # Write the new symbol to the tape, $tape[$tapeIndex] = $rules[$rNum][3]; # Shift the tape to the new index, $tapeIndex += $rules[$rNum][4]; # and make sure it hasn't run past the left edge of the tape. if ($tapeIndex < 0) { $tapeIndex = 0; } # If the machine nears the end of the allocated tape, and more tape is allowed, expand the tape. if (($tapeIndex >= @tape-2) and (@tape < $tapeMax)) {                push(@tape, "_"); }           # If the head runs past the right end of the tape, keep it on the right end. if ($tapeIndex >= $tapeMax-1) { $tapeIndex = $tapeMax-1; } $changed = 1; # Once we've made a transition, we can stop and begin looking for the next one. last; }    } } if (defined($accepts{$state})) {   # Print that it accepts and quit. print "The machine accepts the string.\n"; exit; } print "The machine does not accept the string.\n"; exit; sub readLBA {    my (%states, %accepts, %alphabet, @rules, @tapeBound); open(INFILE, shift) or die "Can't open machine file: $!"; # Discards the section header, ; my $line = ; chomp($line); my @words = &parse_line('\s+', 0, $line); for (@words) {       # records the state names for checking the rules, $states{$_} = 0; }   # Discards the header, ; my $startState = ; # takes the whole line as the start state, chomp($startState); # and makes sure that the start state is defined in the list of states. defined($states{$startState}) or die "The start state $startState isn't a state!"; # Discards the header, ; $line = ; chomp($line); # breaks up the line into state names, @words = &parse_line('\s+', 0, $line); for (@words) {   # checks to make sure that the accept states are defined states, defined($states{$_}) or die "$_ isn't a state!"; # and defines those names in a new hash. The use of a hash makes it easier to determine later if a specific state name accepts or not. $accepts{$_} = 1; }   # Discards the header, ; $line = ; chomp($line); # breaks up the line into alphabet symbols (note that the symbols can be of arbitrary length), @words = &parse_line('\s+', 0, $line); # e is used as the empty symbol in the rules. $alphabet{e} = 1; for (@words) {       # This records which symbols are in the alphabet for checking the rules. $alphabet{$_} = 0; }   # Discards the header, ; $line = ; chomp($line); # breaks up the line into two parts - the "slope" and the "intercept". @words = &parse_line('\s+', 0, $line); # and stores them in the @tapeBound array $tapeBound[0] = $words[0]; $tapeBound[1] = $words[1]; # Discards the header, ; # This variable synchronizes the position of each rule in the rules array. my $rulesCounter=0; while() {   # breaks each rule into start state, input symbol, stack symbol, end state, and new stack symbol. chomp($_); @words = &parse_line('\s+', 0, $_); # checks that the first four pieces are defined in the state and alphabet hashes, defined($states{$words[0]}) or die "$words[0] isn't a defined state!"; defined($alphabet{$words[1]}) or die "$words[1] isn't defined in the alphabet!"; defined($states{$words[2]}) or die "$words[2] isn't a defined state!"; defined($alphabet{$words[3]}) or die "$words[3] isn't defined in the alphabet!"; # and converts the left/right instruction into a number to be added to the position counter. if (($words[4] eq "left") or ($words[4] eq "-1")) {            $words[4]=-1; }        elsif (($words[4] eq "right") or ($words[4] eq "+1")) {            $words[4]=1; }        else {            (die "$words[4] isn't left, right, -1, or +1!"); }   # then creates an array of each rule. for (0..4) {            $rules[$rulesCounter][$_] = $words[$_]; }       # The synchronization variable has to be updated. $rulesCounter++; }   # Reading complete, the subroutine closes the file and returns the name of the start state. close INFILE; # The relevant data is stored in the $machine structure and returned to the main routine. my $machine = {        rules      => \@rules, accepts   => \%accepts, alphabet  => \%alphabet, startState => $startState, tapeBound => \@tapeBound };    return $machine; } sub readInput {    my (@tape, %alphabet, $alphaRef, @tapeBound, $boundRef); open(INFILE, shift) or die "Can't open ".$input.": $!"; $alphaRef = shift; %alphabet = %{$alphaRef}; $boundRef = shift; @tapeBound = @{$boundRef}; # The first line of the file is read as the initial state of the tape, with symbols delimited by spaces. my $line = .""; chomp($line); @tape = &parse_line('\s+', 0, $line); # This makes sure every symbol in the input string was defined in the machine's alphabet. for (@tape) { defined($alphabet{$_}) or die "$_ in $input isn't in this machine's alphabet!"; } close INFILE; my $tapeMax = @tape*$tapeBound[0]+$tapeBound[1]; return ($tapeMax, @tape); }
 * 1) !usr/bin/perl
 * 1) Grabs the filenames for the machine and the word to be run on it.
 * 1) We use subroutines to parse and verify the data in the input files.
 * 2) The machine data is stored in the $machine structure as the keys rules, accepts, alphabet, and startState.
 * 1) Rules and accepts are extracted from the $machine structure for ease of access.
 * 1) This reads the input file and parses it into an array of strings, with each element being one input symbol.
 * 2) It checks to make sure the elements are all in the machine's alphabet.
 * 1) $changed records whether or not a rule has been used when running through the rules list to make transitions.
 * 1) $state is the state the Turing Machine is in, and is initialized to the start state from the machine file.
 * 1) $tapeIndex is the position of the machine's head on the tape.
 * 1) Now that the machine is initialized, we can begin making transitions
 * 1) As long as things keep changing, keep cycling through the rules.
 * 1)            print "::$rules[$rNum][0]??$branches[$i][0]";
 * 2)            print "::$rules[$rNum][1]??$string[$branches[$i][1]]";
 * 3)            print "::$rules[$rNum][2]??".${$branches[$i][2]}[@{$branches[$i][2]}-1]."::\n";
 * 1)            print "State: ".$state." -> ".$rules[$rNum][2]."\n\n";
 * 1) When there are no more possible transitions, if the machine is in an accepting state,
 * 1) Otherwise, print that it does not accept, and quit.
 * 1) This subroutine reads the machine data from the specified file into variables (mostly hashes).
 * 1) This block reads the list of states from the machine file.
 * 1) This block reads the start state from the machine file.
 * 1) This block reads the list of accepting states from the machine file.
 * 1) This block reads the list of symbols in the alphabet from the machine file.
 * 1) This block reads the linear bound on the tape size from the machine file.
 * 1) This block reads the state transition rules from the machine file.
 * 1) This subroutine reads the starting tape from the specified file into an array of symbols.

Previous | Next


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample LBA inputs

= Sample LBA Inputs =

These examples are for use with the perl LBA emulator provided at the bottom of ../Context Sensitive Languages/. That page also contains a description of what a LBA is and how it works.

This machine accepts strings of the form $$\{a^{n}b^{n}c^{n}d^{n}|n \ge 0\}$$. Note that in this example, the input must be bounded by one "_" on each side as a tape delimiter.

start findA findB findC findD reset halt :Start State: start :Accept States: halt :alphabet: _ a b c d $ :tape bound: 1 0 :rules: start    _     findA     _     right findA    $     findA     $     right findA    a     findB     $     right findA    _     halt      _     left findB    $     findB     $     right findB    a     findB     a     right findB    b     findC     $     right findC    $     findC     $     right findC    b     findC     b     right findC    c     findD     $     right findD    $     findD     $     right findD    c     findD     c     right findD    d     reset     $     left reset    $     reset     $     left reset    a     reset     a     left reset    b     reset     b     left reset    c     reset     c     left reset    d     reset     d     left reset    _     findA     _     right

Some sample inputs: These accept: _ a a a b b b c c c d d d _

_ _

_ a b c d _

These reject: _ a a a b b b c c d d d _

_ a c _

_ a b b c c d d _

back


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/Unrestricted Languages

= Unrestricted Languages =

As the name implies, the class of unrestricted languages is the least restrictive class in the Chomsky Hierarchy, and is the set of languages generated by unrestricted grammars. Unrestricted grammars are grammars composed of a finite number of rules of the form A -> B, where A and B are strings of terminal and non-terminal symbols, and A is not the empty string. The languages produced by these grammars are also referred to as recursively enumerable, as a recursive function could theoretically generate all the strings in them, although not necessarily in a finite time.

Turing Machines
Equivalent to the class of unrestricted languages is the class of languages recognized by a Turing machine. A Turing machine (TM) is identical to an LBA (see ../Context Sensitive Languages/), with one exception: a Turing machine's tape is infinite. In its standard form, the Turing machine's tape has a left endpoint but continues indefinitely to the right. Other infinite models for the tape, such as a tape infinite in both directions, or multiple infinite tapes, are equivalent to the standard form.

The Turing Machine is the most powerful machine in the hierarchy, with the power to emulate any of the other machines. It is equivalent in power to most programming languages, although computers only contain finite memory, while a true Turing Machine has infinite memory.

Universal Turing Machine
Turing Machines can also be programmed as something called a Universal Turing Machine (UTM), a single TM (meaning a single set of states, rules, and alphabet) that can accept as input another TM encoded as a string, together with an input string. The Universal Turing Machine can then emulate the other TM running the input string. This universal emulation of its own class is a property not shared by any other machine in the hierarchy. Some of them can be programmed to emulate a specific subset of their class, but none of them can emulate any given member of their class.

Looping
However powerful they may be, they do have limitations. One of the most obvious limitations is that unlike LBAs, a TM has an infinite number of conditions, due to the infinite tape. This means that the TM can not only loop, it can be in an infinite running, non-halting pattern that never loops. As an example, consider a naively programmed TM designed to take as input a positive integer a and to determine if the square root of a is rational by calculating it and printing it out on the tape. If that machine is given the number 2 as input, it will never complete printing the irrational number $$\sqrt{2}$$, and so will run forever.

Examples
The code below is a sample TM emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.

The syntax is: progname.pl TMFile inputFile, where TMFile is a text file containing the TM instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of TM instructions for a machine to multiply two numbers, can be found under ../sample TM inputs/

A sample TM emulator in Perl.

Previous | Next


text:
Computability and Complexity/Formal Languages/Chomsky Hierarchy/sample TM inputs

= Sample TM inputs =

These examples are for use with the perl TM emulator provided at the bottom of ../Unrestricted Languages/. That page also contains a description of what a TM is and how it works.

This machine accepts strings of the form $$\{\_^{+}1^{+}\_1^{*}\_^{*}\}$$. It creates a new string of ones whose size is the multiple of the sizes of the original two, then it halts and accepts. In essence, it is a multiplying machine. If only one string of ones is present, then the size of the resulting string will be zero. Note that with this TM emulator, new tape sections are initialized to _, so _ is essentially a blank character.

start passFirst readSecond passSecond writeThird passThirdLeft passSecondLeft resetSecond readSecond passFirstLeftA passFirstLeftB clearSecondA clearSecondB halt :Start State: start :Accept States: halt :alphabet: _ 1 + = :rules: start		1	passFirst	_	right start		_	start	       _	right passFirst	1	passFirst	1	right passFirst	_	readSecond	_	right readSecond	1	passSecond	+	right readSecond	+	readSecond	+	right readSecond	_	resetSecond	_	left passSecond	1	passSecond	1	right passSecond	_	writeThird	_	right writeThird	1	writeThird	1	right writeThird	_	passThirdLeft	1	left passThirdLeft	1	passThirdLeft	1	left passThirdLeft	_	passSecondLeft	_	left passSecondLeft	1	passSecondLeft	1	left passSecondLeft	+	readSecond	+	right resetSecond	+	resetSecond	1	left resetSecond	_	passFirstLeftA	_	left passFirstLeftA	1	passFirstLeftB	1	left passFirstLeftA	_	clearSecondA	_	right passFirstLeftB	1	passFirstLeftB	1	left passFirstLeftB	_	start	       _	right clearSecondA	_	clearSecondB	_	right clearSecondB	1	clearSecondB	_	right clearSecondB	_	halt	       =	left

Some sample inputs: These accept: _ 1 1 _ 1 1 1 1 _

_ 1 1 1 1 1 _ 1 _

This input will cause the machine to run forever without looping: _ _ _

This input will reject: _ = _

back


text:
Computability and Complexity/Formal Languages/Other Language Classes

= Other Language Classes = The language classes in the ../Chomsky Hierarchy/ do not represent an exhaustive list of the possible language classes. There are many other classes that have been defined since, many of which are defined primarily by a machine that recognizes them, and not by a simple or well-defined grammar.

One example of such a class is the /Counting Languages/.

''Note: There should be more examples here.

For a much larger list of language classes, see Complexity class.

Previous | Next


text:
Computability and Complexity/Formal Languages/Other Language Classes/Counting Languages

= Counting Languages =

Definition
The set of counting languages is the set of languages that can be generated by a counter automaton, a deterministic finite automaton (DFA) (see Regular Languages) with a finite number of infinite counters. These counters can be incremented or decremented during state transitions, and their statuses can be used to determine transitions.

Position in the Hierarchy of Language Classes
If the counters are unused, a counter automaton is equivalent to a DFA, so the regular languages are a subset of the counting languages. There are also context free languages that are counting languages (such as {anbn | n ≥ 0}), context-free languages that are not counting languages (Chomsky says so but never gives an example), and context-sensitive (but not context-free) languages that are counting languages (such as {anbmanbmccc | n,m ≥ 0}). A linear bounded automaton (see Context Sensitive Languages) can emulate a counter automaton by assuming that the counters cannot reach values greater than the length of the input string, and thus can store the counter information in an amount of space linearly based on the size of the input string. The rest of the CA is essentially a DFA, which LBAs can also emulate in linear space. Linear space plus linear space is still linear, so the counting languages are a subset of the context-sensitive languages, and intersect but are not nested with the context-free languages.

Example
The code below is a sample CA emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.

The syntax is: progname.pl CAFile inputFile, where CAFile is a text file containing the CA instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of CA instructions for a machine to recognize $$\{a^{n}b^{m}a^{n}b^{m}ccc|n,m \ge 0\}$$, can be found under ../sample CA inputs/.

Previous | Next


text:
Computability and Complexity/Formal Languages/Other Language Classes/sample CA inputs

= Sample CA inputs =

These examples are for use with the perl CA emulator provided at the bottom of ../Counting Languages/. That page also contains a description of what a CA is and how it works.

This machine accepts strings of the form $$\{a^{n}b^{m}a^{n}b^{m}ccc|n,m \ge 0\}$$.

q1a q1b q2a q2b q3 q4 q5 q6 q7 :Counters: m n :Start State: q1a :Accept States: q7 :alphabet: a b c :rules: q1a c q5 q1a a q1b -> m++ q1b a q1a -> m++ q1a b q2b -> n++ q1b b q2b -> n++ q2a b q2b -> n++ q2b b q2a -> n++ q2a c q5 m==0 q2a a q3 m>0 -> m-- q2b a q3 m>0 -> m-- q3 a q3 m>0 -> m-- q3 b q4 m==0 n>0 -> n-- q4 b q4 n>0 -> n-- q4 c q5 n==0 q5 c q6 q6 c q7 Some sample inputs: These accept: a b b b a b b b c c c

c c c

a a a a c c c

These reject: a a b b a b b c c c

a a b a a b c c

a a a c c c

back


text:
Computability and Complexity/Computability

= Computability =

This page is in need of development.

Computability Theory is the branch of computer science concerned with determining whether a certain problem is solvable. Problems can be thought of as very basic situations or questions.

In this day and age we are surrounded by advanced computers which work at dizzying speeds; it is easy to assume that given enough memory or processing power a computer could compute any problem. However, through mathematics we can prove that there are certain problems which simply do not have clear solutions. For example: when given the problem "What is the last digit of Pi?" it is impossible to find a solution because Pi is infinitely long.

When measuring the "difficulty" of computing a solution, a concept known as "Automata Theory" can be helpful both for calculations as well as comprehension of the problem. Automata Theory will be covered further on in this book - it is a central component in understanding complexity.

Automata Theory
When discovering what may or may not be computable, it is helpful - and indeed, perhaps necessary - to construct models which express the logic behind our computation. Models allow us to plot out exactly how a problem was answered, and allows us to examine every step of the process.

Automata are one kind of model, we can think of them as a kind of machine which represents a problem (such as what is 2 + 2) and then when given some input ( 4 ) runs through a series of steps and either accepts the input as valid, or denies it. This idea (does the input match the given constraints?) is very powerful - and when used sequentially can solve all computable problems.

Automata theory was influenced by the functionalist philosophical movement. Rather than considering mathematics as utilizing numbers which in turn represent values, functionalists preferred to think of numbers as merely being symbols which were manipulated by various rules. When we examine Automata you will see many letters rather than numbers - this is because we are regarding the letters as symbols which themselves hold no inherent importance, and are simply manipulated by the rules we supply. This concept will being to make more sense as you grow more comfortable working with Automata.

The image shown at right is an example of an Automata. It accepts -AKA returns 'true' - if the input matches the constraints a(bc)*d (one 'a' followed by any number of 'bc's and then a single 'd').

Let's examine this image. Each circle is known as a state, each state is given a name qN where n is the identifying number. If we imagine Automata as representing our own mental arithmetic, we can think of each state as being what step in our logical thought pattern we are in. The arrows which point to the different circles are known as "transitions" and lead from one state to another if certain conditions are met. Depending on what kind of Automata you are working with these conditions may vary. In the example given, the only constraint is that our model sees the specified character at the point in the input currently being examined.

For a(bc)*d, the first thing we should check is whether or not the input contains an 'a' at the beginning. If we see an a, we move to the second state. ....

Previous | Next


text:
Computability and Complexity/Computability/Decidability

= Decidability =

This section discusses the decidability of problems run on Turing machines (TMs). For the definition of a Turing machine, see Unrestricted Languages.

Turing Recognizability
Those languages for which there is a Turing machine that will always halt and accept in a finite amount of time for any string in the language are called Turing recognizable languages. Note that it need not be possible to make a machine that halts and rejects all strings not in the language - the machine may loop. Continuing the previous example, the language composed of all {strings giving instructions (with some specific encoding) on how to produce and print as a decimal a number with a finite number of decimal places} is Turing recognizable. If a machine is given a correct input, it can follow the instructions, print the number, finish, and accept. If it is given instructions that don't make sense, it can reject. But if it is given instructions that look right, and follows them, it will run forever.

Decidability
There are some languages for which a Turing machine can be written that will halt on all input, either to accept or reject. These languages are called decidable languages, and TMs that always halt on any input are called Deciders. One example of a decidable language is the language whose words each consist of a stringified LBA together with an input string, where the LBA halts on that input. A TM can be written to emulate an LBA, recording the number of steps it makes, and accept if it accepts, reject if it rejects, and reject if it exceeds a certain number of steps (what that number of steps is and how it guarantees that the LBA will loop forever are explained in the chapter on Context Sensitive Languages). All decidable languages are also by definition Turing recognizable.

The Halting Problem
Perhaps the most important undecidable problem for a TM is known as the halting problem. A universal Turing machine (UTM) cannot always accurately predict whether a given TM will halt or run forever on a given input. Clever programming of the UTM can sometimes predict the answer, but the only solution for all problems is to emulate the machine on the input. Unfortunately, if the emulated machine runs forever, so will the UTM, and will never halt and reject. It has been proven that no TM can be written that can decide the halting problem, so the language consisting of stringified TMs with input strings, where the machine halts on that input string is a Turing recognizable language, but is not decidable.

Non-Recognizability
Not all languages can even be recognized. Take, for example, the inverse of the halting problem, the language whose words consist of a stringified TM with an input string, where the TM does not halt on that input. If that language was Turing recognizable by some TM 'S', then a UTM 'T' could be designed to emulate S, and to also emulate the TM being fed to S. Eventually, one of the two will halt, and thus T will be a decider for the halting problem, which we know doesn't exist, so the language is not Turing Recognizable. Furthermore, since every Turing Machine can be encoded as a unique string under some encoding, and there are a countably infinite number of strings, but an uncountably infinite number of languages, there must be an uncountably infinite number of languages to which there is no corresponding TM, and thus are not Turing Recognizable.

Previous | Next


text:
Computability and Complexity/Computability/Reducibility

= Reducibility =

This page has yet to be developed.

Previous | Next


text:
Computability and Complexity/Complexity

= Computational Complexity =

Complexity theory is a central field of theoretical computer science and has had large impact on all of computer science. Complexity theory tries to find out how many resources (time, space, energy,...) are needed to perform a particular task or to solve a particular problem. It tries to classify problems into complexity classes such that problems in the same class have similar requirements on the resources needed to solve them. For instance, all problems belonging to the complexity class $$\mathcal P$$ have, by definition, an algorithm that solves them relatively fast, that is, in polynomial time.

When we speak of solving a particular problem, we might have in mind the problem of deciding whether a given input graph is connected. This problem can be formalized in a mathematical way as the set $$L = \{ G | G \text{ is connected} \}$$, that is, the set of all connected graphs. We say that an algorithm solves a problem $$L$$ if it returns yes if the input is a member of $$L$$ and no if not. In our example, the algorithm solving $$L$$ would read some input graph, compute something, and then just say yes if it has found out that the input graph is connected. What is beautiful about this framework is that the set $$L$$ is the problem that we want to analyze.

Given a problem $$L$$, natural questions are:
 * How fast is the fastest algorithm that solves $$L$$?
 * How much space (e.g. hard drive) does the best algorithm solving $$L$$ need?
 * If I do not have much space (on ancient mobile phones, say), can I still find an algorithm for $$L$$? Do I then still have the fastest possible?
 * Assume that you have a very hard problem $$L$$, for which you just cannot figure out how to solve it efficiently? Can you prove that it cannot be solved efficiently?

This page has yet to be developed.

Previous | Next

title: Computability and Complexity/Complexity


text:
Computability and Complexity/Complexity/Time Complexity

= Time Complexity =

This page has yet to be developed.

Previous | Next


text:
Computability and Complexity/Complexity/Time Complexity/P

= P =

We can classify all the computational problems into 2 categories, that can be solved by algorithms and that cannot be solved. Although some problems can be solved, we may not be able to solve them in reasonable amount of time. The problems which can be solved are classified in to P and NP. There are other classifications also, but we shall concentrate on P and NP. These classifications are known as complexity classes. Generally speaking, the class P contains problems which can be solved in a reasonable amount of time and NP contains those which cannot be.

The complexity class P
$$ \text{P}=\bigcup_k \text{TIME}(n^k) $$

The complexity class P contains problems that can be solved in a bounded time. The algorithms for solving such problems are bounded by a polynomial function of the input size. The complexity has two parts, a fixed part and a variable part. The fixed part will not depend on any thing else, it is a constant for a given algorithm, but the variable part varies across different instances of the same problem, for e.g. we know that the time taken by a sorting algorithm to sort ten numbers is not the same as the time taken for sorting hundred numbers. Usually the time/space taken by an algorithm will depend on the size of the input to a problem. We can express the time/space taken by an algorithm as the sum of a constant and a polynomial function of the input size. The problems, whose algorithms to solve them, has a complexity that can be expressed as a polynomial, belong to class P. Obviously P stands for polynomial.

Previous | Next


text:
Computability and Complexity/Complexity/Time Complexity/NP

= NP =

This page has yet to be developed.

Previous | Next


text:
Computability and Complexity/Complexity/Time Complexity/NP-Complete

= NP-Complete =

This page has yet to be developed.

Previous | Next


text:
Computability and Complexity/Complexity/Space Complexity

= Space Complexity =

This page has yet to be developed.

Previous | Next


text:
Computability and Complexity/References and Further Reading

= References and Further Reading =

[1] Chomsky, Noam. "On certain formal properties of grammars". Information and Control (2): 137-167, 1959.

[2] Sipser, Michael. Introduction to the Theory of Computation. Second Edition. Course Technology, 2005.

Further Reading:

Complexity Class on wikipedia

Formal Language on wikipedia

Chomsky Hierarchy on wikipedia

Computational Complexity Theory on wikipedia

Caltech's Complexity Zoo wiki

Previous | Next


text:
User talk:DasBrose

Welcome message
Hello, and welcome to Wikibooks!

Here are some tips to help you get started:
 * To learn the wiki-markup-language syntax, see Help:Editing.
 * You should sign your name on Talk and vote pages using four tildes, like this: ~~~~
 * There is a box at the top of the edit window that will insert this, too; it looks like part of a signature.
 * Remember to conduct any editing experiments in the sandbox.
 * You can tell the community something about yourself in your userpage.
 * You can get to this page by clicking the tab at the top of the page labeled with your registered username.
 * If you are a Wikipedian, see Wikibooks for Wikipedians for a primer on how things work here (it's a little different).
 * If you want to base your work here on materials from Wikipedia, please use WB:RFI (requests for importation) to bring the material over in compliance with the GFDL.
 * If you're an instructor and plan on using Wikibooks for a class project, see Guidelines for class projects
 * Please say hello at the Staff Lounge with any questions or ideas.
 * Eventually, you might want to read the Manual of Style and Policies and Guidelines.
 * Please take a look at Naming policy before starting a new book.
 * Remember to maintain a Neutral point of view.
 * Explore, be bold in editing pages, and have fun!

You will find more resources in Community Portal. If you want to ask a question, visit the Study help desk, the Staff lounge, IRC channel or ask me personally on my talk page. For site news, see the Bulletin board. It might be a good idea to add this page to your "watchlist" so that you can see when any new information is posted there. You can do that by clicking the tab labeled "watch" at the top of the page.

Good luck! --Panic 22:30, 9 May 2007 (UTC)

title: User talk:DasBrose


text:
User talk:Djgrunge~enwikibooks

hello djgrunge, welcome to wikibooks! I see that you've created a link to ME4. Unfortunately, this page is not part of a book. If you want to make a page in a book, you need to create a link to Book Name/ME4 instead. If you need help, don't hesitate to ask. --Whiteknight (talk) 23:05, 9 May 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Djgrunge. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Djgrunge~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:10, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 04:53, 19 April 2015 (UTC)

title: User talk:Djgrunge~enwikibooks


text:
Astrodynamics/Ballistic Trajectories

A ballistic trajectory is an orbit that intersects the surface of the earth. Once in the trajectory, a ballistic missile can travel large distances around the earth before impacting with the target.

Suborbital Trajectories
Suborbital trajectories are ballistic trajectories that have their apoapsis above the boundary of space.

title: Astrodynamics/Ballistic Trajectories


text:
Astrodynamics/Lunar Trajectories

In order to get to the moon, a satellite or rocket needs to escape the Earth's gravity (a hyperbolic orbit). Once in the area of influence by the moon's gravity, the satellite needs to have enough velocity to enter into a stable orbit around the moon.

title: Astrodynamics/Lunar Trajectories


text:
Astrodynamics/Interplanetary Trajectories

Since the 1960's, unmanned spacecraft have been sent to planetary bodies outside of the Earth-moon system. These missions present unique problems in astrodynamics.

Patched Conic Approximation
The patched conic approximation is a method used to simplify trajectory calculations by assigning each body their own "sphere of influence". When an object is inside the sphere of influence of a bigger body, only the gravitational force between the object and the bigger body is accounted for. This simplifies a complex n-body problem into a bunch of much simpler two-body problems, whose solutions are the simple conic sections of kepler orbits.

While this approximation can be useful for things like interplanetary trajectories, it fails to model things like lagrangian points.


text:
Adventist Youth Honors Answer Book/Flag folding

 * 1) Have two people stand on either end of the flag, holding a corner in each hand.
 * 2) Fold the flag in half twice, length-wise.
 * 3) Beginning at the striped end, fold one corner into the opposite side of the flag, forming a triangle.
 * 4) Repeat this triangular folding until only a small strip of the star field shows.
 * 5) Tuck this strip into the triangle.

Be sure to keep the flag from touching the ground while folding.


text:
Adventist Youth Honors Answer Book/Flag protocol

Flag protocol defines the proper placement, handling and use of flags. Some countries have added certain protocols into their law system while others prefer to have "guidelines" without civil or criminal consequences attached.

General guidelines are accepted practically universally.
 * General guidelines:

Much of the flag protocol is derived from common sense. That is, using it as a table cover or wrapping paper are inappropriate uses. It should be treated with respect. Many countries consider signing a flag disrespectful, adding a border would be more appropriate. Pinning or sewing items to a flag would also be ill advised.

The flag of honor, that is the nation's flag in most cases, is flown on the center mast if possible. It is also correct to fly the flag on its own right. To an observer it would be on the far left. If more than three flags are used, the proper position is as far left from the point of view of an observer. An additional flag may be placed on the right side, but is not necessary. When two poles are crossed, the position of honor is the flag that ends on the left side from the point of view of an observer (the pole will therefore end on the right).
 * On a mast or pole:

In a semicircle, the position of honor is the center. If a full circle is used outside an entrance to an arena or stadium, the position of honor is directly opposite the entrance. If used to line the walls of the arena, the flag should be placed directly opposite the entrance.

 * Hanging:

When flown horizontally, as from a flag pole, the flag should be oriented so that the canton is closest to the top of the pole. If hung against a wall, the canton should be placed in the upper-left corner from the point of view of the observer.

When hung vertically, flags should be rotated so the canton is again closest to the top of the pole. If the flag is displayed against a wall, the canton should again appear in the upper-left corner, which incidentally requires that the flag be both rotated and 'flipped' from its horizontal orientation.

On a vehicle the flag should be affixed securely to the front right of the chassis.
 * Other places:

When placed with a podium or at a place of worship the flag should be hang directly behind or on a pole to the right of the speaker, from the point of view of the audience.

When carried in single file the flag of honor leads.

When flags of many nations are flown the flag of the hosting country should be placed on the left with the rest following in alphabetical order using the language of the host country.
 * Multiple flags:


text:
User talk:155.188.254.1

Regarding edits made during May 10 2007
Thanks for experimenting with Wikibooks. Your test worked, and has now been removed. Please use Sandbox for any other tests you want to do, since testing material in modules will normally be removed quickly. Please see the welcome page if you would like to learn more about contributing to our project. Thanks. If this is an IP address, and it is shared by multiple users, ignore this warning if you did not make any unconstructive edits. Az1568(Talk) 01:44, 10 May 2007 (UTC)

title: User talk:155.188.254.1


text:
User talk:Fleela~enwikibooks

Welcome message
Hello, and welcome to Wikibooks!

Here are some tips to help you get started:
 * To learn the wiki-markup-language syntax, see Help:Editing.
 * You should sign your name on Talk and vote pages using four tildes, like this: ~~~~
 * There is a box at the top of the edit window that will insert this, too; it looks like part of a signature.
 * Remember to conduct any editing experiments in the sandbox.
 * You can tell the community something about yourself in your userpage.
 * You can get to this page by clicking the tab at the top of the page labeled with your registered username.
 * If you are a Wikipedian, see Wikibooks for Wikipedians for a primer on how things work here (it's a little different).
 * If you want to base your work here on materials from Wikipedia, please use WB:RFI (requests for importation) to bring the material over in compliance with the GFDL.
 * If you're an instructor and plan on using Wikibooks for a class project, see Guidelines for class projects
 * Please say hello at the Staff Lounge with any questions or ideas.
 * Eventually, you might want to read the Manual of Style and Policies and Guidelines.
 * Please take a look at Naming policy before starting a new book.
 * Remember to maintain a Neutral point of view.
 * Explore, be bold in editing pages, and have fun!

You will find more resources in Community Portal. If you want to ask a question, visit the Study help desk, the Staff lounge, IRC channel or ask me personally on my talk page. For site news, see the Bulletin board. It might be a good idea to add this page to your "watchlist" so that you can see when any new information is posted there. You can do that by clicking the tab labeled "watch" at the top of the page.

Good luck!

You might also be interested to read our Cookbook policy page, and talk to other Cookbook editors. Webaware talk 02:37, 10 May 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Fleela. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Fleela~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:12, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 04:59, 19 April 2015 (UTC)

title: User talk:Fleela~enwikibooks


text:
User talk:70.70.204.135

Please do not add profanity or copyrighted material to Wikibooks. The material you added to Wikijunior How Things Work/Pulley contained profanity, and the material you added to SA NC Saaste Tech:Modules Mechanical Systems grade 9 was protected by copyright (I found it at http://library.thinkquest.org/27948/pulley.html). Both have been deleted. Thank you for understanding. -- Jomegat 03:19, 10 May 2007 (UTC)

title: User talk:70.70.204.135


text:
Talk:Aspies Book/How to make my life more predictable

= about section "various rules" = I have the feeling that this section could be renamed to use the word "procedures" or "actions" instead of "rules", although I'm uncertain yet, of which word is best to use. Logictheo 06:08, 10 May 2007 (UTC)

= more "actions" in planning =

 * An action called "slow eating" that generally is about nutrition related things like eating slowly, procedure.
 * An action called "basic actions about communication". Might be pretty straightforward for most people, although if people might be in a bad mood they might disregard all these basic rules. Logictheo 08:53, 10 May 2007 (UTC)


text:
The Poetry of Gaius Valerius Catullus/11

=Text & Translation=

Meter - Sapphic Strophe

=Connotations of The Text=

Catullus 11 is an untitled poem by Catullus, typically believed to be the last of the Lesbia poems. The meter is Sapphic strophe. Catullus 11 also touches on the historical events occurring at the time it was written. The various geographical references in the poem can easily be interpreted as the known borders of the Roman Empire during Catullus's lifespan.

=External Links=
 * Catullus 11 A Translation of Catullus 11
 * Carmina Wikibooks Original Sources on Catullus


text:
Talk:Polish/Prepositions as hints to declensions

Untitled
We should add a kogo/czego/co/czegoś/czymś table. When native speakers are asked about declensions, frequently they run a list of these off their tongue and don't realise that this doesn't help the polish learner at all, since the mapping between question words and declensions, and between question words and prepositions is probably very non-1:1. I meant to memorise the kogo/czego table but haven't got around to it yet... Boud 12:11, 10 May 2007 (UTC)

Could someone add a mention of "bliski" (close, near to) to the page? Or if it's not regarded as a preposition, add a note explaining why? "Near" is regarded as a preposition in English, see http://www.dict.org/bin/Dict?Form=Dict1&Strategy=*&Database=*&Query=near where it says "'Near' may properly be followed by 'to' before the thing approached; but more frequently 'to' is omitted, and the adjective or the adverb is regarded as a preposition." Kgoess (discuss • contribs) 21:49, 12 February 2011 (UTC)


text:
Astrodynamics/Orbit Determination

According to basic geometry, any three points can be fit by an elipse. This means that if we have at least three observations of a satellite's position, we can determine the entire orbit. However, the process is not an easy one.

RADAR
RADAR is one of the powerful tools available to observers on earth. A radar installation can determine the position and the velocity of a satellite, with the position being in the topocentric-horizon coordinate system. Once the radar observation has been made, the coordinates can be transformed into the geocentric-equatorial system as such:

 * $$\mathbf{r} = \mathbf{r}_e + \mathbf{p}$$

Where re is the position vector from the center of the earth to the radar installation, and p is the position vector of the satellite from the radar installation.

Determination from a Position and Velocity Vector
A radar installation can measure the position and the velocity of the satellite in a single observation. However, this observation is typically going to be made using the polar variety of the topocentric-horizon system (azimuth and elevation). The position of the satellite is given in terms of a line-of-sight vector, ρ, and the velocity vector is the derivative of that, ρ'  We can find the distance from the center of the earth (converting to the geocentric-horizon system) by:

 * $$\mathbf{r} = \mathbf{r}_e + \mathbf{\rho}$$

And we can find the velocity vector v by:

 * $$\mathbf{v} = \mathbf{\rho}' + \mathbf{\omega}_e \times \mathbf{r}$$

Where ωe is the angular velocity vector of the earth.

Once we have the v and r vectors in the geocentric-equatorial system, we can find all the classical orbital elements.

Determination from 3 Position Vectors
If we have three observations, with each observation representing a position vector, we can determine the orbit of the satellite. We assume that all three position vectors are coplanar, because if they are not it is not a proper orbit and these equations will not yield proper results.

Given three position vectors, r1, r2, and r3, we can apply the gibbsian method to determine the orbit.

Gibbsian Method
For the gibbsian method, we first construct three new vectors, N, D, and S (not to be confused the S unit vector from the topocentric-horizon system). We construct these three new vectors as follows:

 * $$\mathbf{N} = r_3\mathbf{r}_1 \times \mathbf{r}_2 + r_1\mathbf{r}_2\times\mathbf{r}_3 + r_2\mathbf{r}_3\times\mathbf{r}_1$$

 * $$\mathbf{D} = \mathbf{r}_1\times\mathbf{r}_2 + \mathbf{r}_2\times\mathbf{r}_3 + \mathbf{r}_3\times\mathbf{r}_1$$

 * $$\mathbf{S} = (r_2 - r_3)\mathbf{r}_1 + (r_3 - r_1)\mathbf{r}_2 + (r_1 - r_2)\mathbf{r}_3$$

Now, we can find our p and e quantities from these vectors:

 * $$p = \mathbf{D} = \mathbf{N}$$

N and D always have the same direction, so:

 * $$\mathbf{N} \cdot \mathbf{D} = ND$$

 * $$p = \frac{N}{D}$$

 * $$e = \frac{S}{D}$$

Now, we can determine the unit vectors from the perifocal coordinate system, P, Q, and W from the three vectors we already have:

 * $$\mathbf{Q} = \frac{\mathbf{S}}{S}$$

 * $$\mathbf{W} = \frac{\mathbf{N}}{N}$$

 * $$\mathbf{P} = \mathbf{Q} \times \mathbf{W}$$

Now, we have the p and e values, and we also have the necessarily perifocal unit vectors to define the orbit.

Determining Velocity Vectors
If we have the three position vectors, we can determine three corresponding velocity vectors at each position. If we have the D, N, and S vectors, we can define a new vector B such that:

 * $$\mathbf{B} = \mathbf{D} \times \mathbf{r}_i$$

Where the i subscript corresponds to one of the three position vectors. We can also form a scalar value L, in order to make the calculations easier:

 * $$L = \sqrt{\frac{\mu}{DN}}$$

Now that we have our 4 vectors and the scalar L, we can find the velocity at position i as:

 * $$\mathbf{v}_i = \frac{L}{r_i}\mathbf{B} + L\mathbf{S}$$

Determination from 3 Observations
Radar observations aren't always available, but optical observations typically are. Optical measurements are typically made with the right ascension and declination coordinate system, so we will have 6 values: α1, δ1, α2, δ2, α3, δ3. We can define three unit vectors Li as:

 * $$\mathbf{L}_i = \begin{bmatrix}\cos(\delta_i)\cos(\alpha_i) \\ \cos(\delta_i)\sin(\alpha_i) \\ \sin(\delta_i) \end{bmatrix}$$

With the L vectors, we can find the geocentric-equatorial position vector:

 * $$\mathbf{r}_i = \rho_i \mathbf{L}_i + \mathbf{r}_e$$

Dotting this equation with itself gives us a second equation:

 * $$r^2 = \rho^2 + r_e^2 + 2 \rho \mathbf{L} \cdot \mathbf{r}_e$$

We can solve these two equations to find the two unknowns ρ and r. With r, we can find the position vector r along the direction of the vector L.

Finding the Velocity Vector
We can define the derivative of the L vectors using the Lagrange interpolation formula:

 * $$\mathbf{L}' = \frac{2t-t_2-t_3}{(t_1-t_2)(t_1-t_3)}\mathbf{L}_1 +

\frac{2t - t_1 - t_3}{(t_2-t_1)(t_2-t_3)}\mathbf{L}_2 + \frac{2t-t_1-t_3}{(t_3-t_1)(t_3 - t_2)}\mathbf{L}_3$$

 * $$\mathbf{L}'' = \frac{2}{(t_1-t_2)(t_1-t_3)}\mathbf{L}_1 +

\frac{2}{(t_2-t_1)(t_2-t_3)}\mathbf{L}_2 + \frac{2}{(t_3-t_1)(t_3 - t_2)}\mathbf{L}_3$$

We can use these values to find:

 * $$\mathbf{v} = \rho' \mathbf{L} + \rho \mathbf{L}' + \mathbf{r}_e$$

Differential Orbit Correction
We've seen that with a small number of observations we can determine the complete orbit of a satellite. However, the initial measurements that we have taken can be prone to errors. Any errors that we have in our measurements are made all the more large and glaring because we have relied on so few observations. However, if we increase our number of observations, we can use new values to improve our original "estimate" of the orbit. To do this, we use a method called differential orbit correction.

title: Astrodynamics/Orbit Determination


text: Template:Astrodynamics/CS

title: Template:Astrodynamics/CS


text:
A-level Mathematics/AQA/MFP2

Roots of polynomials
The relations between the roots and the coefficients of a polynomial equation; the occurrence of the non-real roots in conjugate pairs when the coefficients of the polynomials are real.

Square root of minus one
$$ \sqrt{-1} = i \,\!$$

$$ i^2 = -1 \,\!$$

Square root of any negative real number
$$ \sqrt{-2} = \sqrt{2 \times -1} = \sqrt{2} \times \sqrt{-1} = \sqrt{2} \times i = i\sqrt{2} \,\!$$

$$ \sqrt{-n} = i\sqrt{n} \,\!$$

General form of a complex number
$$ z = x + i y \,\!$$

where $$ x \,\!$$ and $$ y \,\!$$ are real numbers

Modulus of a complex number
$$ |z| = \sqrt{x^2 + y^2} \,\!$$

Argument of a complex number
The argument of $$ z \,\!$$ is the angle between the positive x-axis and a line drawn between the origin and the point in the complex plane (see )

$$ \tan{\theta} = \frac{y}{x} \,\!$$

$$ \arg{z} = \theta \,\!$$

$$ \arg{z} = \tan^{-1}{ \left ( \frac{y}{x} \right ) } \,\!$$

Polar form of a complex number
$$ x+ iy = z = |z|e^{i\theta} = \left ( \sqrt{x^2 + y^2} \right ) e^{i\theta} \,\!$$

$$ e^{i\theta} = \cos{\theta} + i\sin{\theta} \,\!$$

$$ z = |z|e^{i\theta} = |z| \left ( \cos{\theta} + i\sin{\theta} \right ) \,\!$$

$$ e^{i\theta} = \frac{z}{|z|} = \frac{x + iy}{\sqrt{x^2 + y^2}} \,\!$$

Addition, subtraction and multiplication of complex numbers of the form x + iy
In general, if $$ z_1 = a_1 + ib_1 $$ and $$ z_2 = a_2 + ib_2 $$,

 * $$ z_1 + z_2 = (a_1 + a_2) + i(b_1 + b_2) $$

 * $$ z_1 - z_2 = (a_1 - a_2) + i(b_1 - b_2) $$

 * $$ z_1 z_2 = a_1 a_2 - b_1 b_2 + i(a_2 b_1 + a_1 b_2)$$

Complex conjugates
$$ \mbox{If } z = x + iy \mbox{, then } z^* = x - iy \,\!$$

$$ zz^* = |z|^2 \,\!$$

Division of complex numbers of the form x + iy
$$ \frac{z_1}{z_2} = \frac{z_1}{z_2}\frac{z_2^*}{z_2^*} = \frac{z_1 z_2^*}{|z_2|^2} $$

Products and quotients of complex numbers in their polar form
If $$ z_1 = (r_1,\mbox{ } \theta_1) $$ and $$ z_2 = (r_2,\mbox{ } \theta_2) $$ then $$ z_1 z_2 = (r_1 r_2,\mbox{ } \theta_1+\theta_2) $$, with the proviso that $$ 2 \pi $$ may have to be added to, or subtracted from, $$ \theta_1 + \theta_2 $$ if $$ \theta_1 + \theta_2 $$ is outside the permitted range for $$ \theta $$.

If $$ z_1 = (r_1,\mbox{ } \theta_1) $$ and $$ z_2 = (r_2,\mbox{ } \theta_2) $$ then $$ \frac{z_1}{z_2} = \left ( \frac{r_1}{r_2} ,\mbox{ } \theta_1 - \theta_2 \right ) $$, with the same proviso regarding the size of the angle $$ \theta_1 - \theta_2 $$.

Equating real and imaginary parts
$$\mbox{If } a + ib = c + id \mbox{, where } a \mbox{, } b \mbox{, } c \mbox{ and } d \mbox{ are real, then } a = c \mbox{ and } b = d \,\!$$

Coordinate geometry on Argand diagrams
If the complex number $$z_1$$ is represented by the point $$A$$, and the complex number $$z_2$$ is represented by the point $$B$$ in an Argand diagram, then $$|z_2 - z_1| = AB \,\!$$, and $$\arg{(z_2 - z_1)}$$ is the angle between $$\overrightarrow{AB}$$ and the positive direction of the x-axis.

Loci on Argand diagrams
$$|z| = k$$ represents a circle with centre $$O$$ and radius $$k$$

$$|z-z_1| = k$$ represents a circle with centre $$z_1$$ and radius $$k$$

$$|z-z_1| = |z-z_2|$$ represents a straight line — the perpendicular bisector of the line joining the points $$z_1$$ and $$z_2$$

$$\mbox{arg }z = \alpha$$ represents the half line through $$O$$ inclined at an angle $$\alpha$$ to the positive direction of $$Ox$$

$$\mbox{arg}(z-z_1) = \alpha$$ represents the half line through the point $$z_1$$ inclined at an angle $$\alpha$$ to the positive direction of $$Ox$$

De Moivre's theorem
$$\left ( \cos{\theta} + i\sin{\theta} \right )^n = \cos{n\theta} + i\sin{n\theta} \,\!$$

De Moivre's theorem for integral n
$$ z + \frac{1}{z} = 2 \cos{\theta} $$

$$ z - \frac{1}{z} = 2i \sin{\theta} $$

Exponential form of a complex number
$$\mbox{If } z = r(\cos{\theta}+i\sin{\theta})\mbox{, } \,\!$$

$$\mbox{then } z = re^{i\theta} \,\!$$

$$\mbox{and } z^n = \left ( re^{i\theta} \right )^n = r^ne^{ni\theta} \,\!$$

$$\cos{\theta} = \frac{e^{i\theta}+e^{-i\theta}}{2} $$

$$\sin{\theta} = \frac{e^{i\theta}-e^{-i\theta}}{2i} $$

The cube roots of unity
The cube roots of unity are $$1$$, $$w$$ and $$w^2$$, where

$$ w^3 = 1 \,\!$$

$$ 1 + w + w^2 = 0 \,\!$$

and the non-real roots are

$$ \frac{-1 \pm i\sqrt{3}}{2} $$

The nth roots of unity
The equation $$ z^n = 1 $$ has roots

$$ z = e^{\frac{2k \pi i}{n}} \mbox{ where } k = 0,1,2, \dots,(n-1) $$

The roots of zn = α where α is a non-real number
The equation $$ z^n = \alpha $$, where $$ \alpha = re^{i\theta} $$, has roots

$$ z = r^{\frac{1}{n}}e^{\frac{i(\theta+2k\pi)}{n}} \mbox{ where } k = 0,1,2, \dots,(n-1) $$

Definitions of hyperbolic functions
$$ \sinh{x} = \frac{e^x - e^{-x}}{2} $$

$$ \cosh{x} = \frac{e^x + e^{-x}}{2} $$

$$ \tanh{x} = \frac{ \sinh{x} }{ \cosh{x} } $$

$$ \operatorname{cosech}{x} = \frac{1}{ \sinh{x} } $$

$$ \operatorname{sech} = \frac{1}{ \cosh{x} } $$

$$ \coth{x} = \frac{1}{ \tanh{x} } $$

Hyperbolic identities
$$ \cosh^2{x} - \sinh^2{x} = 1 \,\!$$

$$ 1 - \tanh^2{x} = \operatorname{sech}^2{x} \,\!$$

$$ \coth^2{x} - 1 = \operatorname{cosech}^2{x} \,\!$$

Addition formulae
$$ \sinh{(x+y)} = \sinh{x}\cosh{y} + \cosh{x}\sinh{y} \,\!$$

$$ \cosh{(x+y)} = \cosh{x}\cosh{y} + \sinh{x}\sinh{y} \,\!$$

Double angle formulae
$$ \sinh{2x} = 2\sinh{x}\cosh{y} \,\!$$

$$ \begin{align} \cosh{2x} & = \cosh^2{x} + \sinh^2{x} \\ & = 2\cosh^2{x} -1 \\ & = 1 + 2\sinh^2{x} \end{align} \,\!$$

Osborne's rule
Osborne's rule states that:

 * to change a trigonometric function into its corresponding hyperbolic function, where a product of two sines appears, change the sign of the corresponding hyperbolic form

Note that Osborne's rule is an aide mémoire, not a proof.

Differentiation of hyperbolic functions
$$ \frac{d}{dx} \sinh{x} = \cosh{x} $$

$$\frac{d}{dx} \cosh{x} = \sinh{x} $$

$$ \frac{d}{dx} \tanh{x} = \operatorname{sech}^2{x} $$

$$ \frac{d}{dx} \sinh{kx} = k\cosh{kx} $$

$$ \frac{d}{dx} \cosh{kx} = k\sinh{kx} $$

$$\frac{d}{dx} \tanh{kx} = k\operatorname{sech}^2{kx} $$

Integration of hyperbolic functions
$$ \int \sinh{x} \, dx = \cosh{x} + c $$

$$ \int \cosh{x} \, dx = \sinh{x} + c $$

$$ \int \operatorname{sech}^2{x} \, dx = \tanh{x} + c $$

$$ \int \tanh{x} \, dx = \ln{\cosh{x}} + c $$

$$ \int \coth{x} \, dx = \ln{\sinh{x}} + c $$

Logarithmic form of inverse hyperbolic functions
$$ \sinh^{-1}{x} = \ln{\left ( x + \sqrt{x^2 + 1} \right )} $$

$$ \cosh^{-1}{x} = \ln{\left ( x + \sqrt{x^2 - 1} \right )} $$

$$ \tanh^{-1}{x} = \frac{1}{2}\ln{\left ( \frac{1+x}{1-x} \right )} $$

Derivatives of inverse hyperbolic functions
$$\frac{d}{dx} \sinh^{-1}{x} = \frac{1}{\sqrt{1+x^2}}$$

$$\frac{d}{dx} \cosh^{-1}{x} = \frac{1}{\sqrt{x^2-1}}$$

$$\frac{d}{dx} \tanh^{-1}{x} = \frac{1}{1-x^2}$$

$$\frac{d}{dx} \sinh^{-1}{\frac{x}{a}} = \frac{1}{\sqrt{a^2+x^2}}$$

$$\frac{d}{dx} \cosh^{-1}{\frac{x}{a}} = \frac{1}{\sqrt{x^2-a^2}}$$

$$\frac{d}{dx} \tanh^{-1}{\frac{x}{a}} = \frac{1}{a^2-x^2}$$

Integrals which integrate to inverse hyperbolic functions
$$\int \frac{1}{\sqrt{a^2+x^2}} \, dx = \sinh^{-1}{\frac{x}{a}} + c$$

$$\int \frac{1}{\sqrt{x^2-a^2}} \, dx = \cosh^{-1}{\frac{x}{a}} + c$$

$$\int \frac{1}{a^2-x^2} \, dx = \tanh^{-1}{\frac{x}{a}} + c$$

Calculation of the arc length of a curve and the area of a surface using Cartesian or parametric coordinates
$$ s = \int^{x_2}_{x_1} \sqrt{ 1 + \left ( \frac{dy}{dx} \right )^2 } dx = \int^{t_2}_{t_1} \sqrt{ \left ( \frac{dx}{dt} \right )^2 + \left ( \frac{dy}{dt} \right )^2 } dt $$

$$ S = 2 \pi \int^{x_2}_{x_1} y \sqrt{ 1 + \left ( \frac{dy}{dx} \right )^2 } dx = 2 \pi \int^{t_2}_{t_1} y \sqrt{ \left ( \frac{dx}{dt} \right )^2 + \left ( \frac{dy}{dt} \right )^2 } dt $$

title: A-level Mathematics/AQA/MFP2


text:
User talk:200.13.22.154

Thanks for experimenting with Wikibooks. Your test worked, and has now been removed. Please use Sandbox for any other tests you want to do, since testing material in modules will normally be removed quickly. Please see the welcome page if you would like to learn more about contributing to our project. Thanks. Mattb112885 (talk) 14:48, 10 May 2007 (UTC)

title: User talk:200.13.22.154


text:
Talk:Haskell/Classes and types

Comment by Kevin S. Van Horn
Isn't the diagram at the end in error? There's no instance of MonadPlus IO.

 * Hmm... worth asking the wikibook at haskell dot org list. Maybe somebody can go fix it -- Kowey 16:31, 20 May 2007 (UTC)

I took the text discussing Haskell classes vs. OO classes out of its "note" box because it doesn't display properly on the Safari and Firefox web browsers -- the note box overlaps the table of contents, rendering the paragraph unreadable. -- Kevin S. Van Horn, 1 July 2007.

Typeclasses /= Interfaces
Be carefull to compare typeclasses to (Java-)interfaces.

I think it is the best way to make people understand typeclasses, by comparing it to structures in other languages, but those people who are coming from object-oriented languages might be confused about the "force to implement" functions, defined in a typeclass.

So I would say typeclasses are more (or equal) to abstract classes in java. I think this would make things easier for java programmers, becoming good Haskell experts :-)

Btw: I am not able to do this minor change in the article. Why can i only edit the Introduction-Part of the article?

 * Sure, go ahead. (Though keep in mind that we also want most of the text to be independent of other languages. That's because analogies can be more harmful than learning the concept from scratch).
 * You should be able to edit any part, look for [edit] links.
 * -- apfeλmus 08:12, 27 January 2011 (UTC)

Rock, paper, scissors
Should they be deriving Ord? --83.226.119.163 (discuss) 18:24, 17 March 2011 (UTC)

"Obviously x and y must be of the same type because you can't add different numbers together."

That's a pretty confusing statement. It sounds like we're trying to tell the reader that 1 + 2 is impossible, because 1 and 2 are different numbers. The author must have meant different numeric types, but even that is not obvious because most other programming languages let you do that.

Merge proposal
Merger rationale: "Classes and types" always looked a bit too short, and now that class constraints are informally introduced very early in the book there is very little reason for the content of this page to remain autonomous. Since there will likely be a few more pages on type classes in this part of the book, merging them will also contribute for a smoother structure. Finally, the proposal has this page as destination because "Classes and types" is a better final title than "Class declarations" (the latter can live on as a redirect). --Duplode (discuss • contribs) 15:25, 11 April 2012 (UTC)

Deriving
"You can only use deriving with a limited set of built-in classes." This is no longer true, see section 7.5.3 here: http://www.haskell.org/ghc/docs/7.4.2/html/users_guide/deriving.html#deriving-typeable

This is a topic that doesn't need to be in the core of a "Learning Haskell" book, but it certainly belongs in the appendix.

Standard classes diagram obsolete?
In the Standard classes section is a very nice diagram. In it, no dependency is shown between Eq and Ord. Yet the immediately preceding section, Class inheritance, describes how there is a dependency between those two classes. I suspect this may be due to the diagram coming from an old edition of the Haskell Report? Gwideman (discuss • contribs) 01:33, 8 February 2013 (UTC)

 * Well spotted! The SVG is fixed now; thank you. Duplode (discuss • contribs) 17:33, 17 August 2013 (UTC)

I think there is also an arrow missing from Fractional to RealFrac. (Sorry, I can't figure out how to edit it myself.) Davjam2 19 Feb 21.

 * Diagram updated, thanks! Duplode (discuss • contribs) 22:10, 19 February 2021 (UTC)

Foreign-looking type declaration
I don't recall seeing this kind of type declaration up until this article:

I'm not sure I understand the meaning of it. Are we naming constructor parameters? If so, for what purpose? Sgcb (discuss • contribs) 00:27, 6 June 2014 (UTC)

 * That is record syntax. It allows us to use the fields of the data type without having to know their position, and also provides convenient getter functions. We cover it in the More on datatypes chapter.--Duplode (discuss • contribs) 18:52, 6 June 2014 (UTC)

 * Oh, gosh, I do remember that now! Thanks for setting me straight Duplode :) Sgcb (discuss • contribs) 20:54, 6 June 2014 (UTC)

 * You're welcome :)--Duplode (discuss • contribs) 01:51, 7 June 2014 (UTC)

New Page, Focussing on Numbers?
Hello - I've been working on a page specifically about numbers. A draft is here. It's still WIP and currently has a few issues (including quite a lot of overlap with this and other pages. It's probably also too long.). I'd be happy to hear any opinions anyone has about it, but will continue with it for now. Thanks. --Davjam2

title: Talk:Haskell/Classes and types


text:
User talk:Maaz45

Thanks for experimenting with Wikibooks. Your test worked, and has now been removed. Please use Sandbox for any other tests you want to do, since testing material in modules will normally be removed quickly. Please see the welcome page if you would like to learn more about contributing to our project. Thanks. -- Herby talk thyme 15:42, 10 May 2007 (UTC)

Please stop adding nonsense to Wikibooks. It is considered vandalism. If you would like to experiment, use the sandbox. Thank you. -- Herby talk thyme 16:00, 10 May 2007 (UTC)

title: User talk:Maaz45


text:
User talk:Nickle~enwikibooks

Hello, and welcome to Wikibooks!

Here are some tips to help you get started:
 * To learn the wiki-markup-language syntax, see Help:Editing.
 * You should sign your name on Talk and vote pages using four tildes, like this: ~~~~
 * There is a box at the top of the edit window that will insert this, too; it looks like part of a signature.
 * Remember to conduct any editing experiments in the sandbox.
 * You can tell the community something about yourself in your userpage.
 * You can get to this page by clicking the tab at the top of the page labeled with your registered username.
 * If you are a Wikipedian, see Wikibooks for Wikipedians for a primer on how things work here (it's a little different).
 * If you want to base your work here on materials from Wikipedia, please use WB:RFI (requests for importation) to bring the material over in compliance with the GFDL.
 * If you're an instructor and plan on using Wikibooks for a class project, see Guidelines for class projects
 * Please say hello at the Staff Lounge with any questions or ideas.
 * Eventually, you might want to read the Manual of Style and Policies and Guidelines.
 * Please take a look at Naming policy before starting a new book.
 * Remember to maintain a Neutral point of view.
 * Explore, be bold in editing pages, and have fun!

You will find more resources in Community Portal. If you want to ask a question, visit the Study help desk, the Staff lounge, IRC channel or ask me personally on my talk page. For site news, see the Bulletin board. It might be a good idea to add this page to your "watchlist" so that you can see when any new information is posted there. You can do that by clicking the tab labeled "watch" at the top of the page.

Good luck! -- Herby talk thyme 16:29, 10 May 2007 (UTC)

Please do not add inappropriate external links to Wikibooks. Wikibooks is intended to be read without the need for external reference and requires content rather than external links particularly those which are for advertising or promotion. Inappropriate links may include (but are not limited to) links to personal web sites, links to web sites with which you are affiliated, and links that exist to attract visitors to a web site or promote a product. If you feel the link should be added to the article, then please discuss it on the article's talk page rather than re-adding it. See the welcome page to learn more about Wikibooks. Thank you. -- Herby talk thyme 16:29, 10 May 2007 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Nickle. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Nickle~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:32, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 05:18, 19 April 2015 (UTC)

title: User talk:Nickle~enwikibooks