Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [computability]

Computability theory a.k.a. recursion theory.

336 questions
Filter by
Sorted by
Tagged with
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 ...
300 views

### Lower bound on number of oracle calls for solving $n$ instances of the halting problem

I encountered the following question, which is an easy exercise (spoiler below). We are given $n$ instances of the halting problem (i.e. TMs $M_1,...,M_n$), and we need to decide exactly which of ...
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, ...
2k views

### Proof for Kolmogorov complexity is uncomputable using reductions

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
312 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)$, ...
846 views

### Decidability of transcendental numbers

I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help. My question is whether it is known that ...
517 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 ...
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 ...
292 views

### Complexity results for Lower-Elementary Recursive Functions?

Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web. The elementary recursive functions ...
431 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 ...
419 views

### A simple proof that decidability of typability in System F ($\lambda 2$) implies decidability of type checking?

Suppose we don't know Joe B. Wells's result from 1994 that both typability and type checking are undecidable in System F (AKA $\lambda 2$). In Barendregt's Lambda calculi with types (1992) I found a ...
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
449 views

### Repeated Quine program

A Quine is a computer program which produces a copy of its own source code as its only output. Is there any Quine program that could print itself out n times, with n specified some way in the program?
374 views

### Relativization with Respect to Non-Recursive Oracles

In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets. ...
458 views

### Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-...
335 views

### Using negative results to prove positive results in computability theory

Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about ...
268 views

### Simply-stated restriction on imperative programming language that captures the elementary functions?

The language of while programs can express the computably enumerable functions. (This is true even if the only arithmetical operations on variables are, say, ...
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, ...
273 views

### Is there any work done on developing difference-calculus of Turing Machines (or simpler Formal Languages)

I am attempting to develop some notions of a difference-calculus between a notional Ideal Turing Machine conceived by a developer (e.g. whatever is intended by a software developer), call it $M_I$, ...
124 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. ...
180 views

### What are considered to be the most canonical and important consequences of the recursion theorem?

The recursion theorem in computability states that, for any computable map $f : \mathbb{N} \to \mathbb{N}$ there exists $n \in \mathbb{N}$ such that $\varphi_{f(n)} = \varphi_n$, where $\varphi$ is a ...
192 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 ...
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") ...
161 views

### Cell probe model vs transdichotomous ram

can someone explain me the difference between those two (cell probe model and transdichotomous ram)? In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of ...
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 ...
1k views

### Is there a generalization of the GO game that is known to be Turing complete?

Is there a generalization of the GO game that is known to be Turing complete? If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is ...
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 ...
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.
795 views

### Universal Turing Machines in “Computational Complexity” by Papadimitriou

The first part of this question has been solved (see comments). In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the ...
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 ...
296 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 ...
621 views

### Was bombe machine turing complete?

In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine. That machine is the Bombe Machine. Is this machine really equivalent to a Turing ...
224 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 ...
219 views

### Complete problems and universal simulator machines

I'm trying to get straight in my mind the relation between complete problems and universal simulator machines. Some notions of computability have universal machines (Turing-computability) and some ...
364 views

### Which model of computation to simulate to prove universality?

I am starting out in theoretical computer science. I have a model of computation based on observations of auto-associative memory in the brain. I believe (with little evidence) that I can do ...
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^*$ ...
183 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 ...
143 views

### What can you do with a moving knife besides cutting a cake?

In the fair cake-cutting, two different computational models are used: A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies; A continuous ...
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 ...
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?
599 views

### Computable function $f = \Theta(g)$ with $g$ uncomputable

This question most likely has a simple answer; however, I do not see it. Let $g:\mathbb{N} \rightarrow \mathbb{N}$ be an uncomputable function and $c$ a positive real number. Can there be a ...
214 views

### Why/when do we ever need transfinite loop variants?

I do not understand why one would ever need a transfinite loop variant. Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates ...
1k views

### Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?

This guy asserts: I’ll say it — the computer was invented in order to help to clarify … a philosophical question about the foundations of mathematics. (This problem being Entscheidungsproblem - ...
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 ...
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 ...
498 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 ...
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 ...
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? ...
An abstract proof system is a polynomial time function $f$ whose range is equal to the set of tautologies. If $\tau$ is a tautology, then an $f$-proof of $\tau$ is any value $\pi$ such that \$f(\pi) =...