Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
20
votes
3answers
2k views

If an abstract machine can simulate itself, does that make it Turing complete?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
16
votes
2answers
3k views

Can chess simulate a Universal Turing Machine?

I am looking to get a definite answer to title question. Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
5
votes
3answers
358 views

Hilbert's Tenth Problem and nonrecursive Diophantine sets

In her paper Defining Integers, Alexandra Shlapentokh presents the following as an immediate corollary of the undecidability of Hilbert's Tenth Problem --- that is, the language $\{p : p$ is a ...
10
votes
3answers
697 views

Computational hardness of “real” computer programs

I have often heard it said that you cannot write a program to catch bugs in a web browser, or word-processor, or operating system, because of Rice's Theorem: any semantical property for a Turing-...
7
votes
2answers
301 views

Simple model of computation with homoiconicity

Is there a simple model of computation with homoiconicity? It would also be nice if, like beta reduction in lambda calculus, every step in execution yields a new valid program. Besides the lack of ...
22
votes
3answers
865 views

Complexity of Tensor Rank over an Infinite Field

A tensor is a generalization of vectors and matrices to higher dimensions and the rank of a tensor also generalizes the rank of a matrix. Namely, the rank of a tensor $T$ is the minimum number of rank ...
11
votes
2answers
1k views

Decidability of equality of CFL's

Following problem is decidable: Given a context-free grammar $G$, is $L(G) = \varnothing$? Following problem is undecidable: Given a context-free grammar $G$, is $L(G) = A^{\ast}$? Is there a ...
14
votes
1answer
283 views

Do there exist groups with word problems in arbitrary P-degrees?

It has been known for a long time that, given any r.e. Turing degree, there is a finitely presented group whose word problem is in that degree. My question is whether the same thing is true for ...
6
votes
0answers
490 views

Prove Post Correspondence Problem Non-Recursive Without Reduction

Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are ...
12
votes
2answers
453 views

Kolmogorov complexity with weak description languages

We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like ...
18
votes
4answers
835 views

Can testing show the absence of bugs?

$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line. How many points are required to uniquely determine a ...
2
votes
2answers
157 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
913 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
871 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
278 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
2k 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
688 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
171 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
353 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
231 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
494 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
264 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
506 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
241 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
239 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
1k 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
873 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
590 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
378 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
371 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
637 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
531 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
882 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
298 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
671 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
2answers
681 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, ...
21
votes
2answers
8k 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
2k 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
473 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 ...
38
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 ...
49
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 ...
6
votes
1answer
279 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. ...

1
3 4 5
6
7