We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
2
votes
2answers
154 views

how to formalize the class(?) of computational models and their equivalence

Introductory books to theoretical computer science usually introduce a the Turing machine and some of its variants, as well as the Random Access machine as computational models. Sometimes more ...
4
votes
1answer
895 views

Why have computer scientists chosen recursor instead of iterator in primitive recursion?

I wonder why computer scientist have chosen recursor instead of iterator (or tail recursor if you like) in primitive recursion, given that function defined in terms of iteration behaves more ...
2
votes
0answers
863 views

Are quantum computers turing complete? [closed]

I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial ...
5
votes
1answer
272 views

Equivalence problem for one-counter automata

I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones? ...
11
votes
1answer
2k views

Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the promise that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
15
votes
2answers
1k views

Explicit mu-recursive expression for Ackerman function

Can you please point out how to build Ackerman function (actually I'm interested in a version proposed by Rózsa Péter and Raphael Robinson) via standard mu-recursive operators? I tried original papers ...
14
votes
2answers
667 views

Dark Integers: General Purpose Computations on Internet Routers

Greg Egan in his fiction "Dark Integers" (story about two universes with two different mathematics communicating by means of proving theorems around of inconsistence in arithmetic) claims that it is ...
1
vote
0answers
170 views

What is the the optimal computational model for memristive style CMOS?

I'm a bit new to the practical use of memristors in general, but I'm starting to see it as a (3D stacked) grid of components that could be treated as transistors or flip-flops on demand (which may be ...
-3
votes
1answer
450 views

What meaning (value) does Gödel's Incompleteness Theorems have for computation theory? [closed]

I've read Gödel's Proof by Nagel & Newman and I feel confused about there philosophical remarks on impossibility of computer to emulate human's mind. I don't understand how does that really ...
6
votes
2answers
352 views

Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

Adding extensions to automata has always been a fruitful domain. But usually, one wants to add weak capabilities, as undecidability comes quickly into the picture. Take FSM with added stacks. It is ...
2
votes
1answer
229 views

Terminology for types of universal computation

Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$. Other models are universal only as far as the input and ...
11
votes
4answers
453 views

Finding a finite model

I know that the question "does a first order formula $\phi$ have a model" is undecidable in general. Could anyone give me a link or a book which give the answer for finite models. If I have a first ...
0
votes
1answer
261 views

Correspondence between Computability & Learnability Theory

Could someone give a brief explanation of the computability & learnability theory & the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are ...
17
votes
3answers
2k views

How do models of hypercomputation overcome the Halting Problem?

Hypercomputation refers to models of computation that are not possible to simulate using Turing machines. (Hypercomputers are not necessarily physically realisable!) Some hypercomputers have access ...
6
votes
0answers
487 views

How fundamental is undecidability? [closed]

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?...
0
votes
0answers
238 views

algorithm that can determine for every regular language L [closed]

can you please tell me how can I show that there exists an algorithm that can determine for every regular language L, whether or not |L| ≥ 5
3
votes
1answer
220 views

Is $ALL\setminus(RE \cup co-RE)$ empty? [duplicate]

Possible Duplicate: Are there languages that are not in RE nor CO-RE? Let $ALL$ be the language of all decision problems. My question is, is there a language that is neither recognizable or ...
16
votes
3answers
980 views

Is there a name for “physical things out of which one can build a Turing machine”?

One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant". People have successfully built computers out of several different substrates -- ...
0
votes
0answers
860 views

Understanding the HRU Model (Protection in Operating Systems)

As of now I am feeling terrible because I have spent the past 10 hours trying to understand this paper titled "Protection in Operating Systems" by Harrison, Ruzzo and Ullman. At this point, any help ...
3
votes
0answers
588 views

Another weird $O(N \log{N})$ Turing machine

This is another question related to the (still open) nice question "Alphabet of single-tape Turing machine" by Emanuele Viola. I describe the question very informally (perhaps it has a trivial ...
6
votes
1answer
361 views

Is there any research on Turing machines with transition relation homomorphic to given algebraic structure?

A Turing machine is defined as a structure $ TM(L,Q,T) $, where $L,Q$ are sets of symbols and internal states of TM respectively, and T is a transition relation: $T: L \times Q \to L \times Q $ for ...
2
votes
2answers
368 views

Time-entanglement phenomenon

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know). The general notion of algorithm is model of ...
5
votes
3answers
628 views

Isolation in Turing-complete reversible cellular automata

I don't know much about the terminology and the results on cellular automata, but I would like to ask a question about an conjecture I thought. Consider Turing-complete reversible cellular automata. ...
17
votes
1answer
2k views

What are the limits of computation in this universe?

I understand that Turing completeness requires unbounded memory and unbounded time. However there is a finite amount of atoms in this service thus making memory bounded. For example even though $\pi$...
32
votes
5answers
2k views

Programming languages for efficient computation

It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard ...
22
votes
5answers
1k views

Problem teaching computability

I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. ...
40
votes
2answers
2k views

Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing ...
9
votes
5answers
509 views

Natural computation based on fundamental forces

Well-known examples of computation inspired by natural phenomenon are quantum computers and DNA computers. What is known about the potential and/or limitations of computing with Maxwell's laws or ...
6
votes
5answers
879 views

Why doesn't computer science follow biology more closely in computer design?

Nature has proved with the brain that it can create complex computers with very little energy consumed and released, extremely low energy compared to a common computer. However, I noticed the design ...
9
votes
4answers
2k views

Why are linear bounded automata not as popular as other automata?

In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, ...
6
votes
2answers
291 views

Reference for checking primitive recursiveness

There is a theorem that states a function $f$ can be computed with a Turing-machine in time $O(g)$ with primitive recursive $g$ (of the length of input) iff $f$ is primitive recursive. Where can I ...
2
votes
1answer
661 views

Undecidable problems not Turing-complete?

are there systems whose nontrivial properties can't be decided by Turing machines, but for which a Turing machine with an oracle able to find out these properties isn't able to solve the Halting ...
-1
votes
1answer
625 views

Is there any way to differentiate between “sort of” Turing-Complete and “really” Turing-Complete?

Some things, like the computer language C, turing machines, lambda calculus, etc. seem to be "naturally" Turing-Complete. That is, they're just Turing-Complete from the bottom up. On the other hand, ...
19
votes
1answer
7k views

How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
12
votes
2answers
1k views

Post Correspondence Problem variant

This is probably pretty simple, but consider the standard Post Correspondence Problem: Given $\alpha_1, \ldots, \alpha_N$ and $\beta_1, \ldots, \beta_N$, find a sequence of indices $i_1, \ldots, i_K$ ...
3
votes
2answers
464 views

Does an infinitely long tape make any difference when proving theorems about Turing Machines?

Standard accounts of Turing Machines in the literature assume an infinitely long tape in at least one direction (and indeed infinitely time long to perform its computations). Clearly in practice no ...
37
votes
7answers
6k views

What do we know about provably correct programs?

The ever increasing complexity of computer programs and the increasingly crucial position computers have in our society leaves me wondering why we still don't collectively use programming languages in ...
48
votes
3answers
2k views

Is there a sensible notion of an approximation algorithm for an undecidable problem?

Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them. For example, the halting problem is undecidable, but practical progress can be ...
5
votes
1answer
271 views

The Complexity of Advice in Computational Indistinguishability

One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc. ...
8
votes
1answer
155 views

Is testing two SO-Horn queries for equivalence decidable?

It follows from Rice's theorem that you cannot determine whether or not two Turing machines decide the same language. My question is: Does this also apply in descriptive complexity settings, ...
-5
votes
1answer
1k views

Alternative Turing Machine Proofs

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me. I am looking for a TM Halting Problem proof that ...
1
vote
2answers
1k views

Is there an alternative proof of the TM Halting Problem other than the “standard” one? [closed]

I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof. Since there are so many formulations of this proof, rather than pick a ...
3
votes
2answers
2k views

What are “$\mu$-recursive functions” and $\mu$-calculus?

I saw in this question a reference to $\mu$-recursive functions or $\mu$-calculus as some computation model equivalent to Turing machines and $\lambda$-calculus. I know about these two but never heard ...
44
votes
5answers
2k views

Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-...
6
votes
3answers
12k views

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
8
votes
0answers
328 views

Are there any models of computation currently being studied with the possibility of being more powerful than Turing Machines? [duplicate]

Possible Duplicate: What would it mean to disprove Church-Turing thesis? Are there any models of computation currently being studied with the possibility of being more powerful than Turing ...
7
votes
2answers
757 views

An example of a totally computable function that is not definable in system T?

Could you give me an example of a totally computable function of type N × N → N that is not definable in System T? Thanks.
8
votes
4answers
856 views

Survey Article on the Theory of Recursive Functions?

Could you recommend a survey article or textbook chapter that introduces the theory of recursive functions? Thanks
5
votes
1answer
399 views

Efficient Algorithm for bilinear pairing on ECC

Bilinear Pairing in the elliptic curves is a wonderful mathematical mapping which is usually defined by the map $e:G_{1} \times G_{1} \rightarrow G_2$ for some groups of $G_{1}$ and $G_{2}$. For ...
7
votes
3answers
1k views

Are there languages that are not in RE nor CO-RE?

I am familiar with the theorem which states that some languages are not in the RE (Recursively Enumerable) class of languages, but that can mean either that they are all in CO-RE (or rather, the part ...