# Recent posts in Theory of Computation

1
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 " ... -main.pdf https://cs.stackexchange.com/questions/85850/minimum-number-of-states-in-dfa-accepting-binary-number-with-decimal-equivalent
2
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{DarkOrange}{\text{Answer = (n+1)*(m+1) + 1}}$ Supported Documents : https://drive.google.com/open?id=1haPRlS78p7RA7ugMhaK9Li6370ZjaEcx
3
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 ... by $\text{LCM}(m,n).$ To find the minimal number of states in the DFA accepting binary strings divisible by $m$ or $n:$
4
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
5
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 ... only- finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.
6
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 ... DECIDABLE(same as above). c) A turing machine replaces the characters on the tape atmost n times on any input SEMI-DECIDABLE(same as above).
7
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
8
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 Problem Set 2
To see more, click for the full list of questions or popular tags.