Recent posts in Theory of Computation

First let me define what is “Divisibility language”.

We have two very similar looking type of languages. I call one type “Length divisibility language” and other I call “Divisibility language” 

"Length divisibility machines/languages" are different from "divisibility languages".

Let me define what I mean by “Length divisibility language” and by “Divisibility language” :

Length divisibility language : Given binary string w, we ask questions like :

(length of w) mod n = r, Or

(#0 in w) mod n = r, Or

(#1 in w) mod n,

etc.

Divisibility language...

Let the i/p alphabet = {0,1} for the following questions :

$\color{red}{Q) \mathbf{About\; String \;Lengths : }}$

$\color{green}{i) \text{ Length of the strings exactly = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{ii) \text{ Length of the strings atmost = n  :  }}\color{blue}{\text{  n+2}}$

$\color{green}{iii) \text{ Length of the strings atleast = n  :  }}\color{blue}{\text{  n+1}}$

$\color{green}{iv) \text{ Length of the strings divisible by n  :  }}\color{blue}{\text{  n}}$

$\color{green}{v) \text{ Length of the strings atleast = m & atmost =...

Lets first prove the number of states in the minimal DFA for accepting binary strings divisible by a given number say $12$

We need $3$ states for checking if a binary number is divisible by $3$ - each state corresponding to remainders $0,1,2.$ Here, remainder $0$ will be the final state for divisibility by $3$. If we add a '0' transition from this state to another state and make it FINAL, we get divisibility by $6$ as a '0' at end ensure number is divisible by $2$ and also retains the property that the number is divisible by $3$ which makes it divisible by $6.$ Add one more state like this and we get numbers divisible by $3\times 2\times 2 = 12.$...

These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear. 

Part 2 is added now...

Decidability Slides Updated

  Day Date Contents Slides Assignments  1  Sep 27 Regular Language- alphabets, language(set of strings), language class or language family
All languages -uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, there is an uncountable recursive set of languages outside recursively enumerable languages 
Finite Automata- Deterministic Automata and Non Deterministic Automata- mathematical representation
Number of DFA's possible with two states over {0,1}
What do you know about...

PLEASE CHECK MY UNDERSTANDING:-

1. Halting Problem:-
a) A turing machine halts after running for exactly k steps on any input
This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

b) A turing machine halts after running for atmost k steps on any input
This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input.

c) A turing machine halts after running for atleast k steps on any input
This is SEMI-DECIDABLE, as we can construct a Turing...

Nice papers with examples:

http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-reductions-rice.pdf

http://people.cs.aau.dk/~srba/courses/CC-08/rice-uk.pdf

Important Ones

https://gateoverflow.in/questions/theory-of-computation?sort=featured

More Questions

http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/assign6/pb9.html

Problem Set 1