The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
2answers
45 views

Analog computers and the Church-Turing thesis

I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine): One class of challenges to the strong Church–Turing ...
1
vote
1answer
58 views

Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
4
votes
3answers
428 views

Rice's theorem vs Turing completeness

I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness. This is the problem: In building an Universal Turing Machine to emulate another ...
6
votes
2answers
454 views

Clear, complete, proof that a language is Turing Compete?

I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete. I have seen web sites that purport to "prove" that SQL is Turing Complete. I have seen a bunch of web sites that ...
3
votes
2answers
142 views

To what does typing correspond in a Turing Machine?

I hope my question makes sense: Starting with the premise that the untyped $\lambda $ calculus is equivalent in power to a Turing machine, to what in a Turing machine does adding types to the $\lambda ...
2
votes
2answers
192 views

Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?

I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning ...
3
votes
1answer
78 views

Upper bound on register machine contents

I am doing some work on register machine theory which revolves around a 2-register register machine and attempting to show that it is not possible to compute an upper-bound on the final contents of ...
-2
votes
3answers
149 views

If set of TM's is not countable?

I was reading about counting principle related to TOC. I understand that the set of TMs are countable infinity. I couldn't understand the significance of it. What is its not countable?
4
votes
1answer
156 views

Time complexity version of the Church-Turing Thesis

There's a lot of debate about what exactly the Church-Turing thesis is, but roughly it's the argument that "undecidable" should be considered equivalent to "undecidable by a universal turing machine." ...
-4
votes
1answer
137 views

Which is the minimal number of operations for intractability?

If we have an algorithm that need to run $n=2$ operations and then halt, I think we could say the problem it solves, is tractable, but if $n=10^{120}$ althought It could be theoretically solvable it ...