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.

Filter by
Sorted by
Tagged with
0
votes
1answer
235 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 ...
9
votes
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?
-2
votes
1answer
598 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 ($...
4
votes
0answers
131 views

Lovasz Theta as a short certificate

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 ...
1
vote
2answers
296 views

Foundational textbook(s) for Complexity and Computability on Real Numbers

It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological ...
4
votes
1answer
194 views

Arithmetic Analogues of P versus BPP

In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there? If there is no such analogy, why is randomness in the resource bounded case ...
1
vote
2answers
206 views

research on systematically attacking multiple instances of undecidable problems

this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint. there are at least ...
14
votes
6answers
770 views

Geometric Interpretation of Computation

Being from Physics, I have been trained to look into a lot of problems from a geometrical point of view. For example the differential geometry of manifolds in dynamical systems etc. When I read the ...
1
vote
0answers
519 views

Is it possible a recursive compression algorithm based on L-systems or a variant?

According to the Internet, there's a way to get an L-system's rules by it's string, unfortunately I can't read it because it's behind a paywall. Question: If that paper is right, is it possible to ...
8
votes
4answers
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 ...
95
votes
15answers
9k views

A simple decision problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
2
votes
3answers
325 views

Is there any programming language in which any equivalent program has a unique, decidable normal representation?

Is there any programming language in which any equivalent program has a unique normal representation, and that normal representation is decidable? Is other words, suppose A and B are programs ...
1
vote
0answers
84 views

What kind of string is produced by successive application of argmax M

Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$. Start with some $\omega_0$. Each subsequent ...
6
votes
1answer
264 views

Is an infinite incomputable sequence random wrt a computable measure?

Take an arbitrary infinite binary sequence $\omega$. The interesting case is when $\omega$ is not computable. Is there a computable (semi-)measure $\mu$ such that sequence $\omega$ is $\mu$-random in ...
0
votes
1answer
221 views

Is there computable function to compute each computable real number?

Recall that a computable real number is one which can be calculated to any precision, like $\pi$ or $e$. It does not matter that these numbers are irrational, computability is about being able to ...
2
votes
1answer
107 views

Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?

I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question: Given a non-deterministic reversal-bounded multicounter machine $M$, is there some ...
9
votes
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 ...
6
votes
3answers
847 views

Computing Functions with Dynamical Systems

I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes ...
3
votes
1answer
153 views

n-approximable functions

I came across the following definition in a paper: We can extend the notion of an $n$-c.e. [n-computably enumerable] set to a notion that measures the number of fluctuations of a function as folows: ...
7
votes
1answer
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 ...
-2
votes
2answers
549 views

how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?

It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem. ...
9
votes
2answers
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 ...
10
votes
2answers
1k views

About Inverse 3-SAT

Context: Kavvadias and Sideri have shown that the Inverse 3-SAT problem is coNP Complete: Given $\phi$ a set of models on $n$ variables, is there a 3-CNF formula such that $\phi$ is its exact set of ...
4
votes
1answer
180 views

Explanation of 1-generic to prove undecidability of halting problem

This question is about an answer in question Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ? Bjørn Kjos-Hanssen answer ...
3
votes
2answers
247 views

Runtime of a TM enumerator

Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)? For simplicity let's say the string ...
5
votes
1answer
1k views

What is a reasonable representation/encoding of objects? [closed]

Question What is a reasonable representation of objects (for computability)? What is the criteria that we should apply to see if a representation is reasonable? This answer by Andrej suggests ...
18
votes
5answers
4k views

Is it possible to test if a computable number is rational or integer?

Is it possible to algorithmically test if a computable number is rational or integer? In other words, would it be possible for a library that implements computable numbers to provide the functions <...
19
votes
1answer
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?
3
votes
1answer
1k views

Langton's ant highway conjecture and undecidability

I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'. I also read that it has been ...
9
votes
2answers
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 ...
8
votes
2answers
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, ...
11
votes
2answers
2k views

The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis

This may be a naive question, but here goes. (Edit -- it is not getting upvotes, but nobody has offered a response either; perhaps the question is more difficult, obscure, or unclear than I thought?) ...
2
votes
0answers
78 views

Efficient asympotically universal predictors

A computable predictor is an algorithm $A$ computing a function $f_A : \{0,1\}^* \rightarrow \{0,1\}$. We regarding the function as providing a predicted continuation of a finite binary sequence. We ...
1
vote
2answers
375 views

Primitive Recursive Isomorphisms

What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive ...
3
votes
1answer
274 views

Are randomly generated infinite patterns computable?

Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the ...
9
votes
1answer
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 ...
5
votes
1answer
256 views

How to describe the set of “all computable functions” using Coq?

Would the set of all computable functions be just the set of all maps of the form f : forall n : nat, P n -> nat where ...
6
votes
2answers
3k views

Was Babbage's Analytical Engine really turing-complete?

According to literature, Babbage's Analytical Engine is turing-complete because it supports conditional branching: it can perform different operations depending on the sign of the result last ...
8
votes
0answers
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 ...
6
votes
6answers
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 - ...
18
votes
2answers
547 views

Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).: If A ...
19
votes
2answers
2k views

What are the limits of total functional programming?

What are the limitations of total functional programming? It is not Turing-complete, but still supports a large subset of the possible programs. Are there important constructs that you could write in ...
13
votes
3answers
699 views

Can any program be implemented mechanically?

Is it possible to build a single purpose (non Turing complete) mechanical implementation of say, Microsoft Word? Is it possible to implement such things as iterators, first-order functions, the whole ...
-3
votes
1answer
705 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
5
votes
1answer
248 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
23
votes
2answers
1k views

To what extent can an algorithm predict the time complexity an arbitrary input program?

The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs. I can, however, certainly write a program that can ...
-10
votes
2answers
632 views

is every “nontrivial” algorithm Turing-complete?

recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS (...
38
votes
7answers
6k views

Applicability of Church-Turing thesis to interactive models of computation

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...
-7
votes
2answers
579 views

Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
-3
votes
1answer
454 views

Help proving a 3CNF related prob. is in P

I need help proving that this problem is decidable in polynomial-time: Input: a 3CNF formula with more than one clause. Question: can the formula be divided into two satisfiable 3CNF formulas ? ...