Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
2
votes
2answers
370 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 ...
2
votes
1answer
231 views

Terminology for types of universal computation

Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$. Other models are universal only as far as the input and ...
2
votes
1answer
170 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 ...
2
votes
1answer
135 views

Turing degree of Solomonoff semi-measure

We define the Solomonoff semi-measure $m$ on finite strings $x$ by $$m(x) = \sum_{p: U(p) = x} 2^{-l(p)},$$ where $U$ is a universal prefix Turing machine, $U(p) = x$ means $U$ outputs $x$ on input $...
2
votes
1answer
502 views

Three questions about finite state machines

Suppose a finite state machine, FSM, has a fixed set of states $S$ and input/output channels $C$, and is uniquely specified by the fixed map $m : S\times D \to S\times D\cup {0}$. If a state $(c_i,s_j)...
2
votes
1answer
96 views

Is there a relativized form of Rice Theorem?

Suppose $P_1$ and $P_2$ are nontrivial semantic properties of Turing Machines, and suppose that $P_1\wedge P_2$ is nontrivial given $P_1$. Can one claim that $P_1\wedge P_2$ is undecidable given an ...
2
votes
2answers
285 views

How to translate general recursion into a set of $\mu$-recursive operator applications?

I'm trying to find a scheme to translate a functional language with let rec into a set of primitives called "generalized arrows", i.e. $\kappa$-calculus with ...
2
votes
1answer
109 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 ...
2
votes
1answer
70 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 ...
2
votes
1answer
86 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 ...
2
votes
0answers
78 views

how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
2
votes
0answers
111 views

Are there analogues of Specker sequences for other complexity classes?

Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...
2
votes
0answers
127 views

A variant of the tiling problem

A classic tiling problem with Wang tiles has the form: Given $n$ tiles $T=\{t_1,...,t_n\}$ and some constraints $H,V\subseteq T\times T$, is there a way to tile a $w\times h$ rectangular grid with $...
2
votes
0answers
58 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 ...
2
votes
0answers
203 views

Computing dual of the spectral norm of tensor of order 3

It is shown in http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf that computing the spectral norm (see Definition 6.6) of a $3^{rd}$ order tensor $T \in \mathbb{R}^{d_1 \times d_2 \times d_3}$ is NP-...
2
votes
0answers
97 views

density of undeciability

Consider a function $f:\mathbb{N} \to \{0,1\}$ whose is defined in terms of some universal Turing machine $U$. If $U$ halts when given $x$ as input then $f(x)=1$, otherwise $f(x)=0$. Clearly the ...
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 ...
2
votes
0answers
189 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.: 111111.....
2
votes
0answers
871 views

Are quantum computers turing complete? [closed]

I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial ...
2
votes
1answer
509 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 ...
2
votes
2answers
2k 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 ...
1
vote
4answers
755 views

Turing-complete computation models on graphs

There are many Turing complete computation models and new ones are devised all the time. I am looking for Turing-complete computation models based on graphs?
1
vote
2answers
1k views

Is there an alternative proof of the TM Halting Problem other than the “standard” one? [closed]

I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof. Since there are so many formulations of this proof, rather than pick a ...
1
vote
2answers
377 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 ...
1
vote
1answer
109 views

How come Wikipedia says that Random Turing Machines can provide uncomputable output?

Wikipedia article mentioned : Hypercomputation The third paragraph starts off with: Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
1
vote
2answers
216 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 ...
1
vote
1answer
111 views

Set of languages that can represent every c. e. languange

Could we find any set of languages $S$, such that it can represent every c. e. languange as it's union, intersection, complement, production(times of element ), and $S\subset X$, where $X\subseteq c.e....
1
vote
1answer
105 views

What is necessary and/or sufficient requirement for a subring of a field to be computable? [closed]

As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring? Conditions on either field or subring are fine.
1
vote
1answer
141 views

Extended Church's thesis and internal parametricity

I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here. Does $Internal\ parametricity \implies ECT$ hold? For forumlation of ECT see https://...
1
vote
1answer
196 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 ...
1
vote
2answers
212 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 ...
1
vote
2answers
227 views

Is true randomness and the physical Church-Turing thesis incompatible?

As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
1
vote
1answer
315 views

Does hyper-computational power of infinite time Turing machines also require infinite memory?

Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
1
vote
2answers
303 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 ...
1
vote
1answer
105 views

What kind of computational model is the brain? [duplicate]

I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine). Another thing that should be a separate question, What would be a perfect computer model ...
1
vote
1answer
109 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 $M$...
1
vote
1answer
291 views

Concerning decidability of a problem on real numbers [closed]

This question is an outgrowth of a certain maths problem I've been thinking about. Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
1
vote
0answers
47 views

Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?

Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
1
vote
0answers
74 views

Logic of learning

Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation? I was Mathematician and Computer Science (dual degree undergraduate) ...
1
vote
0answers
29 views

Non Turing-Complete Models, Conditional-Complete function?

I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of ...
1
vote
0answers
44 views

Is there an alternative technique to define computable functions other than their definition on natural numbers? [closed]

I am not completely sure that why computable functions is defined as a subset of all functions from/to Natural Numbers, but as far as I know, computation comes from real (physical) world so ...
1
vote
0answers
149 views

Solving the Halting problem for most inputs [closed]

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing ...
1
vote
0answers
73 views

Question on Turings Dissertation *Systems of Logic based on Ordinals*, Axiomatic Properties [closed]

I have a question on Alan Turing's Dissertation Systems of Logic Based on Ordinals, a scanned copy you can find here, or rewritten in LaTeX here, and also a copy of the published version here (but in ...
1
vote
0answers
98 views

Relation between MDPs and non-deterministic finite automatons

I'm confused as to the relation (computability-wise) between markov decision processes and NFAs. Are finite state MDPs expressible as regular grammars? If so, are markov decision processes thus ...
1
vote
0answers
162 views

An alternative model of a probabilistic Turing machine [closed]

A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ...
1
vote
0answers
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 ...
1
vote
0answers
528 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 ...
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 ...
1
vote
0answers
171 views

What is the the optimal computational model for memristive style CMOS?

I'm a bit new to the practical use of memristors in general, but I'm starting to see it as a (3D stacked) grid of components that could be treated as transistors or flip-flops on demand (which may be ...
0
votes
2answers
246 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.

1
3 4 5
6
7