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

# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

335 questions
Filter by
Sorted by
Tagged with
790 views

### Fixed points in computability and logic

This question has also been posted on Math.SE, https://math.stackexchange.com/questions/1002540/fixed-points-in-computability-nd-logic I hope it is ok to also post it here. If not, or if it is too ...
311 views

### How high are the higher types that appear in practice?

This is admittedly a rather naively put and vague question, and I'm not sure how much more specific I want or can make it, but I'll try. By "practice" I mean surely in actual programming practice (of ...
832 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 ...
587 views

### For a random oracle R, does BPP equal the set of computable languages in P^R?

Well, the title pretty much says it all. The interesting question above was asked by commenter Jay on my blog (see here and here). I'm guessing both that the answer is yes and that there's a ...
91 views

### Conflicting definitions regarding TM and Recursively Enumerable languages

In Lewis's and Papadimitriou's book "Elements of the Theory of Computation" the transition table is a function $\delta: Q \setminus F \times \Gamma \rightarrow Q \times (\Gamma \cup \{L,R\})$. However,...
171 views

### Computability of infinite-dimensional vector space

So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be ...
104 views

### What is necessary and/or sufficient requirement for a subring of a field to be computable? [closed]

As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring? Conditions on either field or subring are fine.
761 views

### To what extent can the mathematics of Reals be applied to Computable Reals?

Is there a general theorem that would state, with proper sanitization, that most known results regarding the use of real numbers can actually be used when considering only computable reals? Or is ...
107 views

### Consistency and completeness of any arbitrary 3-valued logic? [closed]

Based on the explanations here  I know that 3-valued first order logic has many different versions, which differ in the definition of their operations (e.g. implication). All of these (as far as I ...
176 views

### Decidability of first-order theory of real closed fields with functions

By a famous theorem of Tarski, the first-order theory of real closed fields is decidable, as it admits quantifier elimination. Can this result be extended so that propositions can be quantified over ...
236 views

### How can you prove that all halting probabilites are normal real numbers?

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number. Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable ...
256 views

### Primitive Recursive Definition : Binary numbers

Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. But you obtain algorithms that works with unary numbers. For example, the ...
566 views

### Combinators for the Primitive Recursive Functions

It is well-known that the S and K combinators are Turing Complete. Are there combinators that suffice to yield (only) the primitive recursive functions?
297 views

### Does hyper-computational power of infinite time Turing machines also require infinite memory?

Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
165 views

### How useful is program search in the field of programming-language theory?

I've been thinking: computing systems such as the Lambda Calculus and its variations are usually very simple and can be implemented in as few as ~80 lines of Haskell code. There is a self-interpreter ...
127 views

### A function is lambda-2-definable iff it is HG computable and provably type correct in lambda-PRED2

I'm having a problem regarding Theorem 5.4.40.3 of Barendregt's Lambda calculi with types (1992), a chapter in Handbook in logic in computer science. (I'm referring to the PostScript version available ...
Is the following Busy Beaver variant known? A Universal Turing machine $J$, feeded with a description of a deterministic Turing machine $M_i$, starts simulating $M_i$ on inputs $x_j = 1,2,3,...$ for $... 0answers 129 views ### What is known about reduction by “$P_1$interprets$P_2$” for generalized programming languages? Inspired by this answer, let's say that a programming language is given by the data$L=(P,ev)$where$P$(the set of "valid programs") is a computable subset of$\Sigma^*$and$ev$(the "evaluator") ... 1answer 377 views ### Reversible Turing tarpits? This question is about whether there are there any known reversible Turing tarpits, where "reversible" means in the sense of Axelsen and Glück, and "tarpit" is a much more informal concept (and might ... 1answer 103 views ### Is it possible to determine if a reduction is correct? Suppose we have an arbitrary term, x, in Lambda Calculus, or in an equivalent turing-complete system. Suppose we ask an oracle what is the normal form of that term, ... 2answers 163 views ### Can complexities differ w.r.t. different computational models? I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable ... 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 ... 2answers 405 views ### Complexity of problems solvable by primitive recursion I was wondering if there is any known complexity of problem for which primitive recursive functions cannot solve. One such problem might be "is N the ackermann function for$k_1k_2$" as it seems ... 2answers 224 views ### Would it be possible for a compiler to convert a recursive sum into the average formula? def sum1(n): if n==0: return 0 else: return n + sum1(n-1) def sum2(n): return n*(n+1)/2 A compiler can not convert ... 2answers 396 views ### Is meta-undecidability possible? There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc. In this case I wonder whether a problem can be meta-undecidable. This means (at least in my ... 0answers 197 views ### Computing dual of the spectral norm of tensor of order 3 It is shown in http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf that computing the spectral norm (see Definition 6.6) of a$3^{rd}$order tensor$T \in \mathbb{R}^{d_1 \times d_2 \times d_3}$is NP-... 0answers 241 views ### Is there any system where function equality (extensionality) is decidable? Is there any programming language or system where function equality (extensionality) is decidable? 4answers 1k views ### How to introduce recursion to Simply Typed Lambda Calculus while at the same time keeping strong normalisation? Suppose you have a version of the STLC with one base type, similar to: data Tree = Branch Tree Tree | Leaf Now, suppose you want to add recursion to that ... 0answers 216 views ### Is there a programming language where any arbitrary recursive function can be fused? Compilers like GHC for Haskell use inlining as one of its most important optimising tools. Doing that is not possible for recursive functions, in general. A few techniques have been developed to amend ... 0answers 95 views ### density of undeciability Consider a function$f:\mathbb{N} \to \{0,1\}$whose is defined in terms of some universal Turing machine$U$. If$U$halts when given$x$as input then$f(x)=1$, otherwise$f(x)=0$. Clearly the ... 0answers 168 views ### Exact catchup point between SGH and FGH of ordinals? An ordinal hierarchy is a way to assign a function$f_{\alpha} : \mathbb{N} \rightarrow \mathbb{N}$to each (recursive) ordinal$\alpha$. The corresponding functions are expected to be monotone and ... 1answer 733 views ### Is there any proof that a network made of Turing machines can't solve the halting problem? [closed] My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ... 1answer 221 views ### is determining an unknown CFL from intersection of two CFLs decidable? this problem was asked over a week ago on cs.se now with 7v and no answers so far, ie still "open". (there are many somewhat related problems/near variants re CFLs but its not obvious how to reduce it ... 3answers 980 views ### Proof of undecidability not by reduction from the halting problem The usual way of proving undecidability is by reduction from a RE-complete problem such as the halting problem, validity in first order logic, satisfiability of Diophantine equations, etc. It is ... 4answers 698 views ### Turing-complete computation models on graphs There are many Turing complete computation models and new ones are devised all the time. I am looking for Turing-complete computation models based on graphs? 1answer 633 views ### What is the simplest computational model for which the emptiness problem is undecidable? What is the simplest computational model for which the emptiness problem is undecidable? Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, ... 2answers 458 views ### Problems with efficient solution except for a small fraction of inputs The halting problem for Turing machines is perhaps the canonical undecidable set. Nevertheless, we prove that there is an algorithm deciding almost all instances of it. The halting problem is ... 2answers 898 views ###$\ell_p$-norm preserving Turing machines Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of$\ell_p$-norm preserving machine. For people working ... 2answers 843 views ### How can I compute knots? Is there a documented way to compute knots? (circumferences embedded in a 3-dimensional Euclidean space). I mean, a datatype to represent them, and an algorithm to determine if two instances of the ... 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? ... 2answers 898 views ### Is every recursive language recognized by a mortal Turing machine? We say that a Turing Machine$M$is mortal if$M$halts for every starting configuration (in particular, the tape content and initial state can be arbitrary). Is every recursive language recognized by ... 1answer 107 views ### Is predicting (in the limit) computable sequences as hard as a dominating function? Define a "predicting oracle" to be an oracle that does as described in this question. default (weak) version: Is it the case that, for every predicting oracle$O$, there exists an oracle machine$M$... 2answers 939 views ### Transition Diagram of a Universal Turing Machine I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram? I need this as a reference, so preferably a book or a published ... 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 ... 3answers 1k views ### Is there a complexity theory analogue of Rice's theorem in computability theory? Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable. I am looking for complexity-theoretic Rice-type theorem that tells us which ... 3answers 515 views ### Is the class of primitive recursion functionals equivalent to the class of functions which Foetus proves to terminate? Foetus, if you have not heard of it, can be read up on here. It uses a system of 'call matrices' and 'call graphs' to find all 'recursion behaviors' of recursive calls in a function. To show that a ... 3answers 1k views ### How to make the Lambda Calculus strong normalizing without a type system? Is there any system similar to the lambda calculus that is strong normalizing, without the need to add a type system on top of it? 1answer 234 views ### Simulation of deterministic turing machines What are the best known upper and lower bounds for simulating t steps of certain models of deterministic turing machines (1 tape, 1 tape with read only input tape, 2 tape, multi tape, with/without ... 1answer 597 views ### Intersection between context-free and context-sensitive language decidability [closed] I'm trying to find a formal proof of the following fact: Given a context-free language, say$L_1$, and a context-sensitive language, say$L_2$, it is NOT decidable if their intersection is empty ($...
Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this ...