550 citations · 767 across the 43 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
quant-ph2019
Circuit pedantry
Andreas Blass, Yuri Gurevich
Boolean and quantum circuits have commonalities and differences. To formalize the syntactical commonality we introduce syntactic circuits where the gates are black boxes. Syntactic…
cs.LO2019★ 13 cited
Unconstrained Church-Turing thesis cannot possibly be true
Yuri Gurevich
The Church-Turing thesis asserts that if a partial strings-to-strings function is effectively computable then it is computable by a Turing machine. In the 1930s, when Church and Tu…