Welcome to MSDN Blogs Sign in | Join | Help

Browse by Tags

All Tags » Theory of Computation   (RSS)
Tuesday, June 03, 2008 6:32 PM

Multiplication Circuit for Prime Factorization

Deriving a multiplication circuit for the Prime Factorization problem is trivial if you know how to convert the arithmetic and relational expressions into propositional logic. Below I will show few expressions and their corresponding CNF formulation.
Posted by P.Gopalakrishna | 1 Comments
Attachment(s): MultiplierCircuit.zip
Friday, January 04, 2008 2:43 PM

Remove Data-dependencies

Are you planning to remove data-dependencies in your logic? You might find the below useful. Statement Block Constant Time Equivalent x++; if(x >= MAX_SIZE) x = 0; x = ( x + 1 ) % MAX_SIZE; x--; if(x < 0) x = MAX_SIZE - 1; x = (x + MAX_SIZE – 1)
Posted by P.Gopalakrishna | 1 Comments
Monday, August 27, 2007 4:42 PM

Self-reference Vs. Self-reproduction

As an answer to the question "are there finite mathematical descriptions that are not effective" posed by Hilbert, Turing provided the halting function as being not effectively computable despite being finitely expressible. This he established by devising
Posted by P.Gopalakrishna | 0 Comments
Friday, February 02, 2007 8:44 PM

Establishing the existence of uncountable number of Accelerated Turing Machines

We examine the converse of Church-Turing thesis and establish the existence of uncountable number of Accelerated Turing machines, which leads to the conclusion that these machines are unaffected by Gödel's incompleteness theorem.
Posted by P.Gopalakrishna | 3 Comments
 
Page view tracker