The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
38 views

Curry Howard correspondence and Church-Turing thesis

Curry-Howard correspondence states the equivalence between logic/deduction and types/programs. The Church-Turing thesis states the equivalence of some models of computation. Specifically, all ...
0
votes
1answer
53 views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
0
votes
1answer
68 views

Does Church's Thesis include artificial intelligence?

By Church's Thesis it is impossible to design an algorithm to decide halting problem. I would like to know the word algorithm in this context includes artificial intelligence or not? I mean is it ...
1
vote
2answers
94 views

Why is Oracle Turing Machine important?

As you know, an Oracle Turing Machine (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design ...
1
vote
3answers
123 views

Examples of processes / problems that cannot be tackled by Turing Machines

I know that there are problems that cannot be solved by any algorithm, such as the Halting problem. I also know that some processes cannot be even adequately approximated by any Turing Machine ...
4
votes
2answers
110 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
74 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
470 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
574 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
173 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
225 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
90 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
164 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
168 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
138 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 ...