# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

330 questions
Filter by
Sorted by
Tagged with
91 views

### Enumerator for the language w#w^R? [closed]

I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of ...
240 views

### Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)

The first term is used by Hilbert in his 1928 work, but in Gödel's later work, the same thing is referred to as Unvollständigkeitssatz ("incompleteness theorem"). For today's German CS researchers, it ...
459 views

### In the context of regular languages, must the alphabet be finite?

In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all ...
122 views

### About the origin of the names “immune” and “simple”

I have been wondering for a while about the origin of the names "immune" and "simple". I also posed the same question to Andrea Sorbi, who in turn involved a few more colleagues in the discussion. ...
67 views

### Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain

The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of ...
293 views

### Is the Kolmogorov complexity of the truth tables of the halting problem known asymptotically?

Let $HALT_n$ denote the string of length $2^n$ corresponding to the truth table of the halting problem for inputs of length $n$. If the sequence of Kolmogorov complexities $K(HALT_n)$ were $O(1)$, ...
323 views

### A definition of computable numbers that requires to “wait an infinite amount of time” to get the correct result; how to make this precise

Consider the following definition: A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its ...
3k views

### Importance of irrational numbers in computer science

Computers can only deal with a few rational numbers. Why is it important as a computer scientist to deal with irrational numbers?
125 views

### What is the largest complexity class that a non-Turing complete proof assitant, like Coq, can achieve? [duplicate]

Given that all functions in Coq will terminate, it cannot cover the entire $RE$. So what is the class it can achieve? Is it $R$?
217 views

### Succinct complete problems in DTIME(EXP(EXP(…)))

I understand complete problems for $EXPTIME$ or $NEXPTIME$ formulated as succinct instances of e.g. $NP$-complete problems such as $3-SAT$. On input $x$, one efficiently computes a circuit $R(x)$ such ...
165 views

### Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
187 views

### Is there any relationship of hardness between the two problems?

Assuming F(x,y,D) is a function, and we can evaluate it in polynomial time with input x, y and D. Consider the problem P1: With D as input, computes $(x^*,y^*)=argmax_{(x,y)}F(x,y|D)$ where x and y ...
139 views

### Notions of Computability at Higher Type III

I've recently found a very nice survey paper called "Notions of Computability at Higher Type" by John R. Longley. The paper says it is part of a 3-part series, with the 3rd concerning non-extensional ...
403 views

### Defining primitive recursive functions over general data types

The primitive recursive functions are defined over the natural numbers. However, it seems as if the concept should generalise to other data types, allowing one to talk about primitive recursive ...
119 views

### Are there any known problems that require potential nontermination to solve? [closed]

Apart from problems that specifically have to do with Turing machines, like "Simulate a Turing Machine with the given description", are there any problems that require Turing-complete potentially ...
136 views

### Could you explain to me the reduction? [closed]

I am looking at the following solved exercise: I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why do ...
309 views

### Can all mathematical operations be encoded with a Turing Complete language? [closed]

In High School Computing I was taught the Structured Program Theorem - that you could implement any mathematical operation using: Sequence Selection Iteration After completing a Computer Science ...
133 views

### What is the relationship between tail recursion with other recursions? [closed]

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
107 views

102 views

### What is the simplest universal unidimensional interaction net system?

The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? ...
425 views

### Langton's ant questions

I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless. So that is why I'm asking. 1) Is there a mathematical ...
181 views

### In regards to the tautologies of a polynomially-bounded propositional proof system

In the book 'Logical Foundations of Proof Complexity', co-authored by Stephen Cook, the following definition is given: A proof-system $F$ is said to be polynomially-bounded if there is a polynomial p(...
138 views

### A word anticorrespondence problem

A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ ...
696 views

### Is there a result in computability theory that does not relativize?

I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that Our axiomatization has its limit: it cannot prove any results in computability ...
227 views

### Are there any open problems concerning decidability? [duplicate]

I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.
320 views

189 views

### Applications of “Seemingly Impossible Functional Programs”

What are some practical applications (existing or potential) for Martin Escardo's "Seemingly Impossible Functional Programs"? For starters, here are a few from: Alex Simpson’s Lazy functional ...
82 views

### Proof software for Primitive Recursive Arithmetic

Primitive Recursive Arithmetic is a critical foundational system in mathematics at large, and all the more so in areas studying constructive reasoning and/or computability such as Theoretical Computer ...
153 views

### Can interaction combinators implement any interaction net efficiently?

It is widely known that interaction combinators can implement any interaction net. My question is, can they do so efficiently? I.e., is it possible to prove that there is no interaction net system ...
191 views

### Polynomial-time reductions between undecidable languages

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem. ...
42 views

### Proof for multiplicative dominance of universal probability distribution

I'm looking for the proof of the Leonid Levin theorem that states that the universal prior distribution function multiplicatively dominates all other functions of its type. The original article is ...
847 views

### Computing the DAG of a program given source code or AST

I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG). ...
352 views

### An example where smallest normal lambda term is not fastest

Let the $size$ of $\lambda$-terms be defined as follows: $size(x) = 1$, $size(λx.t) = size(t) + 1$, $size(t s) = size(t) + size(s) + 1$. Let the complexity of a $\lambda$-term $t$ be defined as the ...
55 views

### Simple version of Wang's tessellation problem

I'm reading about Wang's tessellation problem and the text mentions a simpler version: If we consider a finite set of tiles $W_{n}=\{w_{1},...,w_{n}\}$ where $n$ is bounded then the claim is that now ...
197 views

### The halting problem in computational models weaker than Turing machines

What are the main results and/or literature on the (self) halting problem for other machines than Turing machines? Alternatively, what would be the right keywords or tags to search for it. I am ...
203 views

### Information-theoretic Diffie-Hellman

The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand. In Diffie-Hellman Alice and Bob ...
935 views

### Smallest possible universal combinator

I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal ...
145 views

### Undecidable Single Programs [closed]

So the halting problem basically states that there cannot exist any finite length algorithm for automatically verifying if other finite length algorithms terminate. But suppose I start listing out ...
853 views

### Is there algorithmic mathematical analysis?

There are algorithmic graph theory/number theory/combinatorics/information theory/game theory. Is there algorithmic mathematical analysis? According to wiki, mathematical analysis includes the ...
181 views

### Formalized priority argument

A priority argument, an important proof technique in recursion theory, was introduced by Friedberg and Muchnik, to solve Post's Problem, i.e., the existence of two r.e. sets that do not Turing reduce ...
186 views

### Is there any research on approximation of reals with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
125 views

2k views

### Why study type theory?

After reading the literature on type theory (especially the constructive kind - CTT) I'm left wondering "why" should one study type theory, specifically within the confines of "computing" in general? ...