Questions tagged [computability]
Questions related to computability theory, a.k.a. recursion theory
275
questions with no upvoted or accepted answers
1
vote
0
answers
26
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 ...
- 155
1
vote
0
answers
40
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 ...
- 3,752
1
vote
0
answers
140
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).
...
- 133
1
vote
0
answers
79
views
Mathematical resource material accompanying TAPL
I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types.
Prior to this chapter I found the book challenging but ...
1
vote
0
answers
333
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 ...
- 471
1
vote
0
answers
84
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
- 11
1
vote
0
answers
59
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 ...
- 23
1
vote
0
answers
259
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:
...
- 177
1
vote
0
answers
326
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 ...
- 391
1
vote
0
answers
250
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 ...
- 478
1
vote
0
answers
1k
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$...
- 111
1
vote
0
answers
215
views
Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}
I am currently trying to prove whether the above language is decidable, partially decidable or fully undecidable. I am certain that this language is partially decidable and reducible to the halting ...
- 111
1
vote
0
answers
1k
views
trying to understand the diagonal check of 8 queen problem
I was solving the 8 queen problem and tried to look through the internet for comparison solutions to see how my solutions compared to others. I found one very small bruteforce solution that confused ...
- 11
1
vote
0
answers
102
views
How many bits we can negate using two/three NOT gates?
How many bits we can negate using two/three NOT gates ?
I am newbie at this subject so I ask for help. It is about circuits.
Edit
After reading link given in comments by @D.W I think that I can ...
user54001
1
vote
0
answers
368
views
Can cantor pairing function prove that 2D Turing Machine can be represented by 1-tape TM?
I'm trying to figure out if a 2-Dimensional Turing Machine can be represented by any 1-tape TM. I came across the Cantor Pairing Function when doing some research. And based on my understanding and ...
- 151
1
vote
0
answers
230
views
Rice theorem to prove Emptiness problem
Is it possible to use the theorem of Rice to prove that the emptiness problem is undecidable?
With the emptiness problem I mean the question if a certain machine doens't accept any input ?
If you ...
1
vote
0
answers
142
views
trying to prove that HALT is RE-HARD
I'm trying to show that for every $L \in RE $ , there is $L\leq_m HALT$.
can you tell if my reduction is true?
The reduction, while getting input $x\in L$,
builds a T.M machine D, that upon ...
- 11
1
vote
0
answers
62
views
Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?
The question itself:
Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept $\...
- 742
1
vote
0
answers
80
views
turing machine decidability language
I must show that this language is decidable but I think it's not
{D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ }
Here what I think
I give a reduction from E(TM). I suppose that this ...
- 11
1
vote
0
answers
33
views
Filling in the holes of a computable function for reduction
As part of a reduction I am trying to come up with a computable function that will fill in the holes of another function. Suppose $A$ is the set of all $n$ such that $\Phi(x,n)$ halts for all $x \in \...
- 123
1
vote
0
answers
30
views
IsDefined predicate computable?
I am working on a computability assignment, I want to define a helper predicate IsDefined by:
$IsDefinied(x,n) = \{ 1$ if $\Phi^{(1)}(x,n)$ is defined, $0$ otherwise.
Where $\Phi^{(1)}$ is the ...
- 123
1
vote
0
answers
33
views
About the SOS degree of a function and optimization algorithms for the function
Given a non-negative function on the hypercube $f : \{0,1\}^n \rightarrow \mathbb{R}_{\geq 0}$ one says that it is of "SOS-degree" of $d$ (denoted as $deg_{SOS}(f) =d$) if $d$ is the minimum ...
- 493
1
vote
0
answers
24
views
Computing shifted fix point in the BSS model
Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is ...
- 632
1
vote
0
answers
811
views
Showing that $H'$ is not semi-decidable
I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
- 131
1
vote
0
answers
82
views
Undecidability of an existential theory
$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$.
Some theorems (from https://math.stackexchange.com/questions/1382120/ft-has-undecidable-...
- 431
1
vote
0
answers
82
views
How does one calculate the block-sensitivity of a function?
I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity".
Can someone kindly ...
- 1,145
1
vote
0
answers
69
views
Relationship between functions and formal languages?
PR is defined as "the complexity class of all primitive recursive functions"
and also equivalently as "the set of all formal languages that can be decided by such a function". (wiki:http://en....
- 11
1
vote
0
answers
412
views
Show that every infinite recursive set has both a nonrecursive r.e. subset and a non-r.e. subset
My attempt to solve this:
If $\mathcal{A}$ is an arbitrary infinite recursive set then the members of $\mathcal{A}$ can be ordered in ascending order. We can do bijection between $\mathcal{N}$ and $\...
- 11
1
vote
0
answers
99
views
Language accepted by a RAM
Show that any language accepted by a RAM can be accepted by a RAM without indirect addressing.
Could you give me some hints what I could do??
- 431
1
vote
1
answer
48
views
What is the theoretical result of flattening a list containing only itself?
Consider the following python code
X = [None]
X[0] = X
This has many fun properties such as
X[0] == X
and
...
- 11
1
vote
1
answer
354
views
How is the complexity/size of a problem (for instance SAT) determined?
We say an algorithm runs in polynomial time if it is of the form $O(n^k)$ where $n$ is the size of the input, right?
So how do we judge how many inputs there are in: $(x_1 \vee x_2 \vee \overline{x_3}...
- 11
0
votes
0
answers
31
views
Can remainder mod 2 be efficiently computed from addition and equality?
Suppose I have a programming language all of whose variables have natural number type. (So I cannot form higher-type objects, e.g., lists or trees, of natural numbers.) The only atomic commands I am ...
- 101
0
votes
1
answer
78
views
Mapping Reduction from HALT?
I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
- 1
0
votes
0
answers
21
views
Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2
If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
0
votes
1
answer
61
views
recursively enumerable and linear bounded automaton
I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ?
Because LBA has limited tape size so not all recursively enumerable ...
0
votes
0
answers
66
views
Has a Multitape Machine like this been Studied?
Sometimes as a hobby I like to think about different possible "fundamental" abstract computing frameworks, akin for instance to Turing Machines and Lambda Calculus. In particular, I've been ...
0
votes
0
answers
191
views
Turing machine for unary subtraction $m-n$. If $m<n$, the machine writes "$!$" $|m-n|$ times
I am trying to program a Turing machine that performs unary subtraction, $m-n$, but if $m<n$, the machine writes the $!$ symbol on the tape $|m-n|$ times. If $m=1$ and $n=3$, the machine would only ...
- 101
0
votes
0
answers
51
views
Is there a 4th barrier to computing?
I know there are three barriers of computation; the thermodynamic barrier, the light barrier and the quantum barrier. Let’s say we figure out how to send signals FTL, learn how to get rid of excess ...
- 1
0
votes
0
answers
17
views
which phenomena got used to calculate a function that was never computed by digital hardware
or wich phenomena have behavior that can be measured and described as a function between natural numbers but seem to be hard to simulate with digital hardware when the starting conditions are given.
0
votes
0
answers
27
views
Question regarding rice theorem
this is a question I got from a test that we had before
Let there be X, a subgroup of languages above $\Sigma $ such that X isn't empty nor all of the langauges in $\Sigma $ we need to say if the ...
0
votes
0
answers
37
views
Is PrefixFreeNP=P?
I was given the following definition of a verifier:
Verifier $V$ is called $PrefixFree$ if for every $x,y$ such that $V(x,y)=1$, then for every $y'$ (which is not an empty string, $y'\ne\epsilon$) $V(...
0
votes
0
answers
64
views
Undecidability of syntactic properties
Rice's theorem comments on the undesirability of non-trivial semantic properties, however there are syntactic properties that are undecidable as well, such as the "useless" states problem ...
0
votes
1
answer
42
views
If $B \in RE$ then $A \in RE$ - Reduction
I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$.
I also know that Turing Reduction is for Decision, and not Recognition.
Is it possible to ...
- 47
0
votes
0
answers
68
views
If a Turing machine can compute any computable problem how can Turing completeness be achived?
To my knowledge a Turing machine is able to compute anything considered computable.
I got the definition of Turing completeness from this answer Explain the difference between Turing Complete and ...
0
votes
0
answers
45
views
How to think about blank symbol when Turing Machine used as a function?
Turing Machines can be used to compute functions.
For example f(x)=x-1.
0011 is on the tape. Turing Machine computes for some ...
- 299
0
votes
0
answers
20
views
Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$
I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of
$$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
- 101
0
votes
1
answer
75
views
Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language
I've been working on this question for a few hours now and I've been trying to figure out the question above. My biggest problem is that I don't know what to do with the $>$ and $\geq$ symbols when ...
- 1
0
votes
0
answers
52
views
I would not be able to get my simulation in my life time
I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
- 101
0
votes
1
answer
141
views
How are enumerator programs formally defined?
Enumerator programs appear quite often in even an elementary computer science textbook without a formal definition. It does not seem to fit the standard definition of a computable function (through mu ...
0
votes
0
answers
65
views
How should I imagine $M_w[\epsilon]\downarrow$ for the empty halting problem or $M_w[w]\downarrow$
I'm learning about computability problems e.g. reducing the general halting problem to the halting problem on a blank tape. But before I can understand this problem I first have to understand what ...
- 3