Computability theory a.k.a. recursion theory.
3
votes
1answer
80 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: ...
6
votes
1answer
160 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
145 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
212 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 ...
8
votes
1answer
828 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
123 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 ...
3
votes
2answers
168 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 ...
4
votes
1answer
471 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 ...
5
votes
5answers
1k 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 ...
9
votes
1answer
138 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?
2
votes
1answer
175 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 ...
7
votes
1answer
114 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
161 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, ...
8
votes
2answers
473 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
49 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
188 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
183 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
111 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
125 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 ...
3
votes
2answers
250 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 ...
6
votes
0answers
63 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 ...
5
votes
6answers
381 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 - ...
14
votes
2answers
207 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 ...
7
votes
2answers
325 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 ...
12
votes
3answers
545 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 ...
-4
votes
1answer
202 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
205 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)$ ...
14
votes
2answers
371 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 ...
-8
votes
2answers
202 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 ...
21
votes
7answers
3k 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
263 views
Is #P in NP and coNP, simultaneously? [closed]
Is #P in NP and coNP, simultaneously? What follows is a construction that has certificates for up to and including the maximum number of solutions to k-cnfs, but has no certificate for any number ...
-3
votes
1answer
283 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 ?
...
10
votes
1answer
506 views
Feasibility of Gödel machines
Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine
It's a general problem solver which is capable of self-optimization. It's suitable for reactive ...
0
votes
0answers
114 views
Oracle that will provide any computable information about another oracle
Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then ...
2
votes
1answer
294 views
More complex integers
In connection to this question:
Expected values of Kolmogorov complexity in a random sample
Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > ...
4
votes
2answers
188 views
Mathematical explanation of recursion and lambda (referenced in The Little Schemer)
In the preface of Friedman and Felleisen's book The Little Schemer it states:
We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a ...
1
vote
1answer
287 views
Definition of a prefix-free Turing machine
A prefix-free function is one whose domain is prefix-free.
Similarly, a prefix-free (Turing) machine is one whose domain is
prefix-free. It is usual to consider such a machine as being
...
6
votes
1answer
500 views
What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?
I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ripe for such problems"). ...
1
vote
0answers
45 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 ...
2
votes
2answers
161 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 ...
2
votes
2answers
484 views
Is a turing machine with random number generator more powerful?
Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a ...
13
votes
2answers
472 views
Decidability of fractal maze
A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article:
Begin at the MINUS and make your way to the PLUS. When you enter a smaller ...
1
vote
1answer
336 views
Initial conditions for universal Rule 110
In A New Kind of Science, Wolfram proves that the Rule 110 cellular automaton can emulate a cyclic tag system, and is therefore a universal computer.
I was wondering what specific initial conditions ...
2
votes
0answers
136 views
Particle collisions for universal computation
Proof of universality of Game of Life is straightforward (CAFAQ):
(two annihilating glider streams with gaps (ie. 0s) are colliding, one is "data" and the second is all glider filled, ie.: ...
0
votes
2answers
282 views
largest language class for which inclusion is decidable
am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable.
am also ...
13
votes
1answer
614 views
Halting problem, uncomputable sets: common mathematical proof?
It is known that with a countable set of algorithms (characterised by a Gödel number), we cannot compute (build a binary algorithm which checks belonging) all subsets of N.
A proof could be ...
11
votes
1answer
425 views
Programming languages with canonical functions
Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, ...
9
votes
3answers
370 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 ...
6
votes
0answers
123 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 ...
3
votes
1answer
204 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 ...
