Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

0 votes

Constraints on the order of program semantics given by an enumeration of turing-complete system programs

A Tuing-complete programming language has the property that there is a surjection $c : \mathbb{N} \to \mathsf{Prog}$ (the set of all valid programs in whatever model of computation you have). We call $...
Andrej Bauer's user avatar
  • 30.5k
0 votes

Generating all unique (tape content, head position) possibilities for a Turing Machine

It seems to suffice to enumerate all binary strings, mirror/flip each around the least significant digit also (to ensure that all strings prefixed by any number of 0's are generated) and, if the tape ...
2080's user avatar
  • 241
0 votes

Decidability of the language that accepts a universal turing machine

Rice's theorem: Every nontrivial property of the RE languages is undecidable. you are asking about machines M' that recognize the same language as $L_{\mathcal{u}}$: $$ \{ \langle M' \rangle : L(M') = ...
pabloealvarez's user avatar
0 votes

What are quines (layman friendly)?

A fixed point is a solution $x$ to a fixed-point equation $x = f(x)$. The Kleene Recursion Theorem states that there is a Universal Recursive Function $f(P(φ),y)$ that includes every other recursive ...
NinjaDarth's user avatar
0 votes
Accepted

Are there any example of practical application of counter machines?

Random access memory is not based on the RAM model. It's the other way around: the RAM model was inspired by random access memory. The RAM model is an abstraction of modern computers, which is useful ...
D.W.'s user avatar
  • 160k
0 votes

Reduction from $HALT$ to $A_{TM}$

Your solution looks correct. I have a concern that since we have assumed a decider for ATM, so M will either accept any word 'w' or reject it; in either case our constructed decider for HaltTM would ...
harshchy2210's user avatar
1 vote
Accepted

What are the simplest examples of programs that we do not know whether they terminate?

Take any open problem in Number Theory and convert it into a question of whether a given program terminates. E.g. One example that works for the twin prime conjecture is: ...
Daniel Donnelly's user avatar
0 votes

$FINITE_{TM}$ is not Turing-reducible to $A_{MT}$

Point: For simplicity we work with TM whose language contains only numbers. Let's say FINITE is Turing reducible to A. INFINITE = { (M) | M is a TM and L(M) is infinite} Then we can make a TM with an ...
Ali Dastjerdi's user avatar
5 votes

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

It is decidable whether $\epsilon \in L(G)$. Given a context-free grammar $G$, you can construct a new context-free grammar $G'$ such that $L(G')=L(G) \cap \Sigma^+$. If $L(G')=\Sigma^+$ and $\...
D.W.'s user avatar
  • 160k
0 votes

Is the Rice Theorem applicable for these problems?

Just a rule of thumb:- Rice's theorem concerns properties of languages, not the Turing machines. Consider property P as the set of some R.E. languages, P is nontrivial if it does not contains all R.E. ...
harshchy2210's user avatar
1 vote

Prove that a language does not many one reduce to its complement

You won't be able to prove this, because it is false. Let $J$ be an arbtirary undecidable language. Let $L = \{2n \mid n \in J\} \cup \{2n+1 \mid n \notin J\}$. Then $L$ is undecidable, and $L \...
Arno's user avatar
  • 3,103
2 votes
Accepted

Is this formulation for a turing machine proper?

It is fine, but by limiting your transitions to take the machine from $q_n$ to $q_{n-1}$ for every $n$, you severely restrict the power of your machines: they will take exactly $n+1$ steps and then ...
reinierpost's user avatar
  • 5,664
0 votes

Prove/disprove that if $L_1, L_2\in \mathrm{RE}$ then $L_1-\ L_2, L_1 - \overline{L_2}\in \mathrm{RE}$

You can find in the following link RE that RE is closed under the Kleene star operations, concatenation, union, and intersection. However, it is not closed under set difference and complementation. ...
Subhankar Ghosal's user avatar

Top 50 recent answers are included