The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
23 views

Canonical definition of suitable encoding

I've had several Computer Science courses and, from what I recall, I've never been given a rigorous definition of suitable encoding. Definitions always tend to use effective method or some synonym to ...
8
votes
1answer
68 views

Church-Turing and physical PDEs

When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these ...
3
votes
1answer
102 views

Whatever that can be done using algorithm can be done using Turing machine

In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine? Since that period many new algorithms were implemented. What was his ...
0
votes
0answers
42 views

Does Turing Completeness imply the existence of a Universal Program?

Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L ...
3
votes
3answers
742 views

Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing ...
2
votes
0answers
35 views

Problems understanding proof of smn theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
10
votes
3answers
2k views

Is there any uncountable Turing decidable language?

There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?
5
votes
0answers
102 views

Computational power of Actor Model

In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine. In his paper "Actor Model of Computation: Scalable Robust Information ...
4
votes
3answers
205 views

Can every program be parallelized infinitely and automatically?

In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible. And as I have read ...
5
votes
3answers
906 views

Is there an algorithm for converting Turing machines into equivalent Lambda expressions?

We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure. But is there an algorithm, a systematic way for us to convert a Turing machine into ...
2
votes
3answers
141 views

Church-Turing thesis is a dualism

Church-Turing thesis : Every effectively calculable function is a TM-computable function. But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the ...
1
vote
1answer
390 views

Why Turing wasn't wrong? [closed]

Computer science is a science and as a science each thesis can be refutable. So, why there is no "major" counter-thesis? After all, Einstein was a well known "genius" and has lived a long life and he ...
1
vote
2answers
89 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 ...
1
vote
1answer
286 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
124 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
341 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
2answers
192 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 ...
6
votes
2answers
231 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
84 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
531 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 ...
7
votes
2answers
932 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
199 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
314 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
166 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
196 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
180 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." ...
-3
votes
1answer
150 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 ...