Euler's totient function

Its a very nice function on Natural numbers. A totient function on natural number n represented by φ(n) is defined as -
                  For prime p : -
                                 


Clearly φ(n) = # of mutual primes w.r.t n in the range of [ 1 ... n ].

Notation :- Z_n = [ 0 ... (n - 1) ]

Property : - 1. ∀ m,n ∈ Z ( Set of Natural Numbers ) s.t. gcd(m,n) = 1,
                             φ(m.n) = φ(m).φ(n)
                   2. ∀ m,n ∈ Z, φ(m.n) = φ(m).φ(n). gcd(m,n)/φ(gcd(m,n)) 
                   3.       
                   
                  4. For mutually prime a,n
                  5. 
                  6.  For ∀ a,n ∈ Z  and n > 1, 

If we inscribe  Möbius function and then some beautiful identity could be found.

For more see http://en.wikipedia.org/wiki/Euler's_totient_function

Language

In Automata-theory -

Alphabet :- Finite set of symbols.

String :- Sequence of symbols.

Language :- Set of strings.

Operations on Strings :- 
1. (+) - union

2. (.) - concatenation  

3. (*) - Kleene star 

Ex :-  A = "aa" B = "bb" 
1. A + B = {"aa","bb"} 
2. A.B = "aabb"

3. A^* = ε ∪A∪A²…

Notice that A^* the set of all finite strings over A.

Finite permutation of strings and above mentioned operations creates Regular Expression.

Regular Language :- 

Def 1 :- If -
             i. ∃ λ : Σ →  M is a  monoid homomorphism where M is a finite monoid.
             ii. S ⊆ M
then { ω∈ Σ^* | λ(ω) ∈ S} is regular.

Def 2 :- 
Let, L ⊆ Σ^*and there is an equivalence relation ~ s.t uw ∈ L if and only if vw ∈ L for all w ∈ Σ*
The language L is regular ↔  Number of equivalence classes of ~ is finite.

A language L on alphabet Σ is Regular ↔ It is equivalent to a Regular Grammar
↔ It will have an Equivalent DFA ↔ It will have an Equivalent NFA.

Finite Automaton

We already described FA in the previous pages. There are 2 kinds of Finite Automaton, 1. DFA 2.NFA. Here introduced the concept of non-determinism and determinism.

Deterministic FA :- This is a FSM with a input string and a set of Accepting states (F). Formally a 5-tuple (Q,Σ,δ,q₀,F) represents the Structure. Here machine read the symbol , progress head one step right and take a deterministic jump [ A jump where from a current state one can go to a single next state ] from current state to new state with respect to the read symbol.

Non-Deterministic FA :- This is a non-deterministic FSM [ Normally FSM are deterministic but we can also make it non-deterministic by allowing multiple possible next state from current state w.r.t single read symbol . Control would choose totally  randomly  one of the next state from those possible next states, as it could only be in only one state at a time ].

Practically then for each symbol and each current state there will be multiple possible next state and so in a obvious consequence there could be multiple path of control flow and we don't know which path the control will go. But now we can say that the NFA will accept some string if ∃ at least one path ending in a accepting state.

So, formally NFA will also be a 5-tuple same as DFA, only difference is δ: Q × Σ  → 2^Q


With δ we sometime want to see the transition function for a string and we call it δ^'.
It is designed as -
1. ∀ (s,a) ∈ ( ( Σ^*- ε ), Σ ) → δ^'(s.a)  = δ^'(s).δ(a)
2. δ^'(ε) = φ

Finite State Machine

Def :- A Finite State Machine is a mathematical model of computation, as an abstract machine having a finite number of states ( forming set Q ) and transition between them. Also -

1. There is an finite sequence of symbols from a finite alphabet ( Σ = set of symbols ), 
2. One reading head is reading the string in left to right direction. 
3. There is a machine control which reside in only one state at a time. With the change of the time, a new symbol will be fetched from the string, reading head will go right and control moves from current state to next state according to transition function ( δ: Q×Σ → Q ).

Thus a FSM is typically a 3-touple (Q,Σ,δ) but if we inscribe a start state  q₀ , where machine control will initially reside, [ which makes things more convenient ]  then it become a 4-touple (Q,Σ,δ,q₀).

A FSM could be enhanced with adding a few more components. Suppose we add  a finite tape with input symbols and the machine will read one symbol at a time. Now the state transition occur according to the currently read symbol. 

 FSM and FA

Now, its a time to correct little correct ourselves. What I had told so far is obviously FSM but the definition of δ: Q×Σ → Q bound it in only a Deterministic zone. There is also a Non-deterministic FSM where  δ: Q×Σ → 2^Q. That is here the next state for a current state w.r.t a read symbol is not deterministic i.e. a not single state rather a state  randomly chosen from a set of states. 

While adding some more component we can construct some beautiful construct out of this. Let's color some state with a similar color / use flag for them and name them as Accepting State. With respect to a finite string if machine control halt in a Accepting state then we will say that the machine accepted that string. Now the set of acceptable string form a Language which would be accepted by that FSM. 

This above mention structure is called Finite Automaton.    

Lagrange Multiplier

Its a method of Solving optimization problem over Real field with respect to equality constraints.

Let, the problem P is :-

Find max f(x,y)

s.t.  g(x,y) = 0

Now,

1. We will make another function  φ(x,y,λ) = f(x,y) + λ . g(x,y).

2. We can say that  ∀p = (x₀, y₀) ∈ sp(P) [ sp(P) is Solution Space of problem P ] ∃λ₀ s.t. φ(x₀, y₀, λ₀) will be a stationary point.

i.e.  ∀(x₀, y₀) ∈ sp(P) ∃λ₀ ∈ ℜ s.t. φ(x₀, y₀, λ₀) will be a stationary point,
→  ∇_x,y,λ (φ) | _{(x0, y0, λ0)} = 0.

One Example :-

max ( x + y )
s.t. x² + y² = 1

φ(x, y, λ) = x + y + λ ( x² + y² - 1 )
∇_x,y,λ (φ) = ( 1 + λ x ; 1 + λ x ; x² + y² - 1) = 0 = ( 0 , 0 , 0 ) 
→ λ = √ 2 , ( x , y ) =  ( 1/√ 2 ,1/√ 2 )

Footnote of C

In C main components are its keywords, variable & const , functions etc.

• This language have reserve keywords to indicate something. We cannot use these keywords to indicate anything else. 
• Variable :- These are memory blocks to hold values. Each variable has a type. Variables are mutable i.e. change in the variable content will change the content of respective memory block.
• Data type :- A data type represents a system to indicate the type of data, like size and its functionality. We have no class concept in C so in build in libraries the definition of basic data type like int, char, float etc are given. We can build our own data type using typedef, Structure, union and enum .   
• Pointer :-  Pointer is a variable stores the l-value of another variable in the virtual memory. In C pointer has constant size but it also hold the the type of data it is pointing to. We can manipulate the values in the pointed location by a process called de-referencing.  
• Constant is a variable with constant or fixed value. This be stored in static position in function activation, we will see later what is static position.
• Array :- Consecutive memory blocks from same type where the array name is representing a pointer holding the 1st memory address of those blocks. Array are normally statically allocated allocated. They could be dynamically allocated by malloc, calloc, realloc. 
• Structured Programming :- In C part of code inside a '{'  and corresponding '}' represents a block or bundle of code to be executed as a group.  A block represents a complex task  formed by sequence of simpler tasks. Ex. eating could be a block consist of -         
• picking up food by hand, put it in mouth,    
• chew in mouth and pass the food  to digestion system, 
• if  still fill hungry and there is more food  then                                                                           go to the step 1.
C implements block as simply some lines in '{}' or a loop or a function or structure,union, enum etc.

• Pre-process :- C facilitates pre-process using command after '#' directive. In pre-process it defines some strings as something, includes files/headers, check by #ifndef or #ifdef and #endif pairs etc.
• Function  :- C use system stack to implement recursion of repeating code segments. Functions in C is like mathematical functions which take some input and generates some output. We supply some variable's value to the function (Call by value) and it give output to the calling function or manipulate some memory places used/generated by that program or manipulates std streams/files (stdin,stdout,stderr) or some other file in memory.  
• Function Pointer :- In C a function pointer points to the executable code of a function in memory. We can call the function by the function pointer.
• Function Call :- A function is been called by de-referencing its function pointer. Unlike copy-rule of sub-routine here we create an Activation Record holding current values in all local and temporary variables  ( while constant and static as well as global variables  and function's executable codes will be in Static Storage ). Each activation record will have a Current Instruction pointer to the next instruction of the calling function and Current Environment pointer to the calling activation.
• Procedural Code :-  C normally read and execute the program file from the top to bottom ( This is called execution path or control flow direction ). The execution start from 'main' function. From there multiple functions are called in execution path. The function call take the control the called function's executable code. 
• Memory Management :- C normally split the virtual memory mainly in Static, Heap and Stack and Un-allocated zone. The heap and stack are taking their requirement from the Un-allocated zone from both side of it.
  
  Stack consist of data of Activation Records. Heap has dynamic memory allocated blocks.
• Scope and Lifetime :- A variable or functions scope is the span of code up to which it can be accessed [ That is if the control is in the scope of some variable it could be accessed by the control ]. A variable's life time is the range of code till which the variable will hold a position in memory. Nb. A dead variable cannot have scope but the reverse is possible. [1] .

Programming Languages of Digital Computer

When using a digital computer we actually create programs and run them.

Computer :- A machine whose Processing stage in its IPO cycle is nothing but computation.

We call a program as a software normally if it interacts with the user  in direct or indirect way.
You can burn a microprocessor with a program which only consist of an infinite loop and never give  or take any output/input respectively, but that will not be a software.

Programs are sequence of bits to represent a sequence task to be done by Computer. Program are written in some language.

String :- A sequence of symbols belongs to an alphabet corresponding to a language.
Language :- A set of strings generated from the alphabet of that language.
Every language has a grammar.
Grammar :- The set of rules to generate exactly those strings which belongs to that language.

In the computation syntax represent the grammar. A string is syntactically correct  means it is generated following the grammar of that language.

However semantics tells the meaning of the language. It is usually very important to map a string of an language to equivalent string in another language ( Actually 'meaning' has an implicit hint that we want to translate or map the string in an language to some sequence image/symbols residing in out brain i.e. the implicit language of brain ).

For example :- When a person tells to another person  that "I Love You" at that moment the feeling / image of love generates in the person who received that voice. :) But if one say "I want to dance with you." the sequence of dancing moment will rise in your mind.

Practically in the sense of computer science the semantics does only above mentioned work. But for linguistics the semantics also decide validity of a sentence. (But in the computing languages the invalid sentences could not pass the grammar test.)

 Programming languages are a subset of computational languages as one programming language is  valid under a certain environment. Suppose there is no concept of memory allocation in some computing device like PLD , there some code in C language has no meaning. But mostly all well known programming language can work on the common digital computers so we can just avoid this point as we are by default assuming to talking about normal digital computers PC or higher level.

In the context of normal computers the programming language is the set of string in which user can express his wish of some task to be done by that computer and that  could be translated to the equivalent Machine code to execute the desired task.

 




  

Computational Complexity

We know that Touring Machine is something which possess the most power of computation. Now our task is to separate problems in different complexity class to identify their complexities.

We can take problems as per 3 version.
1. Optimization
2. Decision
3. Searching

For example this problem :-
Graph vertex Coloring (G(V,E),F) :-
Given a simple un-directed graph with vertex set V and edge set E and we have to assign color vector F  = (f_v) of size |V| where f_v represent color of vertex v  and for any two vertex the having an edge in between can't have same color.

Optimization version :- Report the min value of  max(f₀,f₁,....f_(|V|-1)) we can ever make.
Searching version :- Report the F for which max(f₀,f₁,....f_(|V|-1)) will be minimum
Decision version :- Report whether a given assignment F is a minimal  assignment found by serching

For the complexity analysis we are going for the Decision version.

We will classify the problems as NL , P , NP, PSPACE, EXPTIME,EXPSPACE and so on...

Let's see them one by one .