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. Converting Arithmetic and Relational expressions to Propositional Logic Here symbols such as x, y, z, a, b, c etc……

# Tag: Theory of Computation

## 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) % MAX_SIZE; x…

## 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 the mechanism of Turing Machine, an abstract machine that captured the logic of thought (see Ref 1). In…

## Establishing the existence of uncountable number of Accelerated Turing Machines

Abstract. 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. The Converse of Church-Turing Thesis In general terms, the Church-Turing thesis asserts that every effectively calculable function is computable by Turing machine. A…