Questions tagged [computability]

Questions related to computability theory, a.k.a. recursion theory

9
votes
0answers
120 views

In the beginning, computable functions where always total, but when where the partial functions included

The modern definition of computable functions $f : \mathbb N \to \mathbb N$ as given on wikipedia quite naturally describes partial functions, and not just total functions. Now I am reading some ...
7
votes
0answers
127 views

Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
6
votes
0answers
88 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
4
votes
0answers
47 views

The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
4
votes
0answers
89 views

Wanted: Concrete Example of Busy Beaver Holdout

I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' ...
4
votes
0answers
100 views

Is a reduced Wang B-machine Turing-complete?

A Wang B-machine has only 4 instructions: right: Move tape head right left: Move tape head left ...
4
votes
0answers
84 views

Undecidable problems with efficient heuristics

Are there some undecidable problems for which there are efficient heuristic algorithms, that succeed on a sufficiently large subset of inputs to be worth using? The one application that comes to mind ...
4
votes
0answers
73 views

Turing reductions by NX ∩ coNX and binary relation problems

Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
4
votes
0answers
53 views

Polynomial Hierarchy and its Relation to Multi-Phase/States Physical Systems

We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to ...
3
votes
0answers
49 views

Is there a name for the class of functions whose totality can be proved using “Ackermann-like” reasoning?

Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion ...
3
votes
0answers
58 views

Is the number of tests needed to know if a program computes the identity computable?

Given a $\lambda$-term $t\in \Lambda$ and an integer $k$, we say that $t$ behave likes the identity when applied to $k$ if $tk\to_\beta^*k$ (where the integer is represented as a church numeral). We ...
3
votes
0answers
71 views

Direct reduction $L_{REG}\le_m L_{CFG}$

Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. ...
3
votes
0answers
91 views

Post's Correspondence Problem - BFS or DFS?

This question has recently occurred to me as I was working on an implementation of the (Bounded) Post's Correspondence Problem. Basically, which method is generally best for PCP? Breadth-first or ...
3
votes
0answers
64 views

Prove that variable projection is recursive

Let $\varphi:\mathbb{N}\to\mathbb{N}^*$ be an arbitrary recursive enumeration of finite strings and $\mathcal{I}^n_i(x_1,...,x_n) = x_i $ be the $i$-th projection over $n$ variables. I would like to ...
3
votes
0answers
47 views

A syntactic property of computing systems: is non-coding DNA universal?

One of the surprising aspect of the genome for lay-people is that it contains important non-coding DNA parts, which does not mean that they are all useless. I never paid so much attention to the fact, ...
3
votes
0answers
163 views

A complete catalog of 2-state Turing machines?

For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a ...
3
votes
0answers
151 views

Is there any programming system that enables reversible computations?

Better explained with examples, I need a programming system with the following characteristics: ...
3
votes
0answers
70 views

The sequence in which every symbol minimizes conditional complexity?

I formulate the question in terms of universal distributions. Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary ...
2
votes
0answers
58 views

Is it a bad idea to require a correctness proof as part of a computable real number?

At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to ...
2
votes
0answers
24 views

Is there a formal way of defining a Zeno Machine?

The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all ...
2
votes
0answers
37 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
2
votes
0answers
159 views

What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
2
votes
0answers
29 views

Semidecidable properties of computable reals

By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I ...
2
votes
0answers
82 views

What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...
2
votes
0answers
165 views

Simulating a turing machine with DPDA with two stacks

In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. ...
2
votes
0answers
31 views

Nearest codeword in a translation-invariant code over $\mathbb{Z}^d$

Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support. Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$. It is possible to calculate the nearest codeword $...
2
votes
0answers
97 views

Is there an analysis of the creation of axioms for a mathematical structure as a computational problem?

Historically, what has happened is the following: There is a "mechanical" structure, most importantly, arithmetic, which operates according to a set of well-defined rules that a stupid computer can ...
2
votes
0answers
46 views

Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
2
votes
0answers
38 views

From SETH to circuit lowerbounds

Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR) In threshold ...
2
votes
0answers
75 views

Is the set of admissible numberings recursively enumerable?

For each admissible numbering, pick at least one pair of programs (but not necessarily all, which is impossible anyway) where the first translates from a given admissible numbering to that one, and ...
2
votes
0answers
149 views

Is the problem that intersection of two cfl is a cfl or not undecidable?

I am trying to use the computation histories argument to fit this. But I am unable to find this as yet.
2
votes
0answers
47 views

Effectively compute bound and period of regular expression on single alphabet

It is known that an infinite language $L\subseteq \{a\}^*$ is regular iff the set $U:=\{x|a^x\in L\}$ is ultimately periodic. (A set $U\subseteq\mathbb{N}$ is said to be ultimately periodic if there ...
2
votes
0answers
123 views

Universal lower semicomputable semimeasure and Coding Theorem

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question. The authors define the reference ...
2
votes
0answers
46 views

When give two encodings rise to the same notion of computability?

To my understanding, the notion of Turing-computability of a partial map $ℕ_0 \dashrightarrow ℕ_0$ depends on the encoding of $ℕ_0$. Say $Σ$ is an alphabet and $γ \colon Σ^\ast → ℕ_0$ is a bijection. ...
2
votes
0answers
63 views

What is the precise mathematical definition of n-iterated recusion?

Primitive recursion can be extended to double-recursion as in the following link: http://www.andrew.cmu.edu/user/kk3n/recursionclass/1primrec.html How can this be generalized to n-iterated recursion?...
2
votes
0answers
307 views

Determining whether a number is a perfect square without computing its square root

One of the interesting results of Number Theory is the theory of quadratic reciprocity. One finds that it is possible to determine whether an equation $x^2 \equiv a \pmod p$ has a solution $x$ without ...
2
votes
0answers
160 views

How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable?

What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a ...
2
votes
0answers
28 views

What is the relation between Universality and simulations of Cellular Automata structures?

Elementary Cellular Automata and Conway's Game of Life show interesting Cellular structures, suppose we have a computational model {a Cellular Auotmaton} that can simulate both CA types (ECA & ...
2
votes
0answers
39 views

What is the relation between Universality and Geometric shapes in cellular automata?

When wolfram described Elementary Cellular Automata, most of the rules appeared as triangle and lines. Now, Rule 110 consists of triangles which is proved to be universal. Is there a relation ...
2
votes
0answers
302 views

Decidable non time constructible function

Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ ...
2
votes
0answers
48 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
1
vote
0answers
22 views

Getting string from phrase structure grammar

For the following phrase structure grammar I want to construct the type of string that satisfy it, but I am not sure the way to go. $$\begin{align*} S &\to xTy \\ T &\to xTT \\ xTx &\to ...
1
vote
0answers
26 views

Theory for programs that are “embedded” in other programs?

We can make the following distinctions: (I will use the term "program" and "machine" as synonyms). A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes ...
1
vote
0answers
42 views

Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960). ...
1
vote
0answers
45 views

Can a CFG generate an accepting configuration? - or is there a turing-recognizable CFG language that is not decidable

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that ...
1
vote
0answers
44 views

product of fully time constructible functions is fully time constructible

How would you prove that product of two fully time constructible functions is fully time constructible? I managed to prove for sum, but product seems more complicated
1
vote
0answers
53 views

Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ...
1
vote
0answers
160 views

Difficulty in reducing non halting problem to a given problem

I am having difficulty in reducing non halting problem to the given problem to prove that language is non R.E For eg Completeness problem of TM . In the above problem, we accept $\Sigma^*$ if H ...
1
vote
0answers
160 views

Unrestricted grammar is closed under intersection

I want to show that unrestricted grammar is closed under intersection and I don't want to use Turing machine or etc. So I think that we have two grammar $G_1$ and $G_2$ that are restricted for example ...
1
vote
0answers
284 views

Converting a non-deterministic context free grammar to deterministic

I have the non-deterministic context free grammar $$I \to abcX | abdY$$ $$X \to X d | \epsilon$$ $$Y \to XX |I$$ and i want to convert it into a deterministic. I know that the rules $I \to abcX | abdY$...