Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
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 ...
12
votes
2answers
402 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 ...
7
votes
2answers
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 ...
6
votes
1answer
263 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 ...
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 ...
9
votes
2answers
291 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 ...
7
votes
2answers
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 ...
16
votes
2answers
2k 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 ...
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 ...
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
83 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 ...
0
votes
1answer
220 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 ...
12
votes
2answers
235 views

Reducing threshold questions to finiteness questions

It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time". In formal languages theory for ...
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 ...
18
votes
4answers
810 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 ...
27
votes
6answers
2k views

How are real numbers specified in computation?

This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
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 ...
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: ...
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
0answers
191 views

Reference Request: Oracle applications outside cryptography

Oracles have been used to prove results in cryptography where all parties have access to a random oracle instantiated with some cryptographic primitive. I am looking for references to papers that have ...
2
votes
3answers
596 views

Template Metaprogramming and Turing Completeness

I am trying to design a Turing Machine using C++ Template Metaprogramming. What steps must be taken to ensure that the code that I'm gonna write will actually build a Turing machine ? I have read that ...
1
vote
2answers
374 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
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 ...
-2
votes
2answers
542 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
297 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 ...
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 <...
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 ...
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'. ...
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?) ...
9
votes
5answers
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 ...
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 ...
9
votes
1answer
418 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 ...
3
votes
1answer
299 views

Abstract definition of universal computation

There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known ...
19
votes
3answers
1k views

Is the concept of the Turing Machine derived from automata?

I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"? I didn't know the answer of course, but I'...
18
votes
2answers
545 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 ...
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 ...
2
votes
2answers
363 views

Difference between Stencil -structures and Cellular Automata Category-theoretically?

Definitions Stencil = "For a given point, a stencil is a pre-determined set of nearest neighbors (possibly including itself)." (source) Wikipedia's definition (source) = It looks ...
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 ...
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 - ...
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 ...
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)$ ...
-3
votes
1answer
704 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 ...
-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 (...
6
votes
1answer
377 views

Term that can distinguish beta-equivalent normal forms in the untyped lambda calculus

I'm trying to work through two (non-assessed) class-work questions and am stuck on a question that seems similar to one I could do. The first question was to prove that there does not exist a $\...
4
votes
0answers
379 views

Are there connections between Turing machines and symbolic dynamic systems?

On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association": $\sigma(\ldots, x_{-1}...
-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 ? ...