Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1,610
questions
1
vote
1answer
12 views
Proving the decidability of whether a CFG generates a particular string or not
Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$.
Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
1
vote
1answer
24 views
High-level description of aTM
If I have language:
L = {x | x = n^2 for some integer n}
How can I give a high-level description of Turning Machine that decides on the language?
1
vote
1answer
43 views
Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?
Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
1
vote
1answer
41 views
How can I show that a language is Turing-recognizable and decidable?
I was wondering how I can show that the language $\{a^n b^n c^n \mid n \geq 0 \}$ is Turing-recognizable. Also, if it is Turing-decidable?
1
vote
1answer
32 views
Give an implementation leveldescription of a TM
L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z}
is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM ...
0
votes
1answer
59 views
Reducing the halting problem for a language with strings that include at least one 1
$L_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence
$L_2$ = Turing machines that decide $L_1$
I think the first language is decideable, as the input string is of finite ...
0
votes
1answer
66 views
Turing Machine to return all prime numbers
My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not.
...
-1
votes
2answers
46 views
Turing Machince
I really need some help with this problem. I'm running into the issue that the input is running out of space to append the 11 or 10. I could really use some help conceptualizing this problem and how ...
-1
votes
0answers
41 views
Turing machine; theory of computation
I'm trying to build a deterministic Turing machine that takes 2 words $w_1, w_2 \in \{a, b, c, d\}^*$ separated in the form of $Bw_1\#w_2B$ and determine whether $w_2$ is a substring of $w_1$.
The ...
2
votes
0answers
12 views
Similarities between Babbage's difference engine and the Turing machine
What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between ...
-6
votes
0answers
50 views
Halting problem proof is wrong, here is why
Instead of solving the halting problem, I will try to solve a less complicated problem in a similar manner.
Can we write a function that will predict if two given numerical inputs are equal.
I will ...
0
votes
1answer
39 views
Decidable questions of undecidable problems
Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
1
vote
1answer
28 views
Is it possible for a Turing machine to halt without reading the complete input string?
Is it possible for a Turing machine to halt without reading the complete input string. Suppose there is a string "adc" preceded and succeeded by infinite number of blanks. Can a Turing machine halt ...
-1
votes
1answer
37 views
How to construct a Turing Machine
Can someone help me to write a Turing Machine that decides whether its input sentence is in a particular language or not? This particular
language generates alternating 01's. If it decides the input ...
2
votes
1answer
29 views
Showing the following language is decidable
Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable.
Generally such questions seem to be ...
1
vote
1answer
18 views
Showing the language of TMs that halt on a decidable set of words is not in RE
I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a ...
0
votes
0answers
28 views
Head Position Function of Oblivious Turing Machines
I am trying to understand oblivious Turing machines. According to the book of Arora and Barak, a TM $M$ is oblivious if the location of each of its heads at the $i$-th step of execution on input $x$ ...
1
vote
1answer
52 views
How to find out the complement of a language of turing machines?
With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example.
L={M∣M is a TM that halts on empty tape after even transition steps}
What's the ...
1
vote
1answer
22 views
Equivalence from multi-tape to single-tape implies limited write space?
Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape:
$A$: "adds a $ at the beginning of the tape."
So we have:
$$
\begin{array}{lc}
\text{...
0
votes
1answer
40 views
Is language {M | M halts and print “Hello World”} recursively enumerable?
Is language {M | M halts and print "Hello World"} recursively enumerable?
I'm not sure my proof is correct.
Let universal Turing machine U start another Turing machine M2 that reads result of work of ...
3
votes
2answers
121 views
What can't you do without Turing-completeness?
I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose.
...
0
votes
0answers
14 views
Functions cumputable in $\theta(n)$ and $\theta(|S| \cdot n)$ for calculating subsets of size |S|
I need to define a function $f: \mathbb{N} \rightarrow \{0,1 \}$ that is computable (by a deterministic TM) in $\theta(n)$ worst case time and such that the time complexity for calculating $f(S)$ is $\...
0
votes
1answer
897 views
Class of languages recognised by a Forgetful Turing Machine
A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $a$, ...
0
votes
1answer
31 views
I want to know where there is the flaw in my argument
I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.
$L: \{\langle M\rangle: M\space is\space a\space TM\space and\...
5
votes
2answers
1k views
How is the problem, {⟨G⟩|G has no triangle} in Logspace?
I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
-1
votes
1answer
60 views
Why is it not possible to prove that two Turing Machines calculate the same function?
I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
0
votes
0answers
47 views
Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?
I found en excercise asking this question.
I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...
1
vote
1answer
49 views
How can $A \cup B$ be decidable if $B$ is undecidable?
My assignment says:
"Determine if the following statement is correct:
If $A$ and $A \cup B$ are decidable, then $B$ is decidable."
The solution says:
"Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...
1
vote
0answers
104 views
Proof by reduction and Turing machines [closed]
This is a practice question I have, but I can't wrap my head around it.
.............
Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}.
B = Blank Position
the ...
0
votes
1answer
69 views
Are computers infallible?
(Not sure if this is the right place to ask this question.)
Let's say I get a computer to calculate 1+1. It should give 2, obviously. Will it always give 2? Is there any possible combination of ...
1
vote
3answers
55 views
Turing machines without time steps?
In "More Is Different," an article about reductionism in science, the author makes the following off hand remark near the end:
I find that at least one further phenomenon seems to be identifiable ...
0
votes
1answer
40 views
Decidability of decision problems
Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear ...
0
votes
0answers
17 views
How to prove this function as onto?
The function $\ f$ : L→B, where $\ f(A)$ equals the characteristic sequence of
A, is one-to-one and onto, and hence is a correspondence. Therefore,
as B is uncountable, L is uncountable as well.
...
2
votes
1answer
31 views
Can't find a mistake in reduction from RE language to a non-RE language
In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I ...
0
votes
0answers
51 views
What Makes A TM undecidable (using Recursion Theorem)
PROOF :We assume that Turing machine H decides ATM for the purpose of
obtaining a contradiction. We construct the following machine B.
B =“On input w:
Obtain, via the recursion theorem, ...
0
votes
1answer
73 views
Why is a subset of a undecidable language decidable?
I have problems with the understanding why a subset of a undecidable language is decidable. We've proved in the lecture that $HALT$$_T$$_M$$=${$<M,w>$|M is a TM and M halts on input w} is ...
1
vote
2answers
70 views
Since the halting problem is undecidable, does that mean that there exists an always undecidable program?
The usual demonstration of the halting problem's undecidability involves positing an adversarial machine (call it $A_0$) that runs the decider machine (call it $D_0$) on itself and performs the ...
0
votes
0answers
12 views
undecidable problems solvable for humans? [duplicate]
are undecidable problems also unsolvable for humans? I mean I would think I could tell by reading the code of a program if it will halt for a certain input (which would solve the haltingproblem).
...
0
votes
1answer
82 views
Rice Theorem - Problem to understand and apply it
I have struggle to understand the Rice Theorem.
My understanding of Rice Theorem:
The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial ...
1
vote
1answer
33 views
How to make Turing machine deterministic?
My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes.
My question is about the productions coming out of state $q_0$:
$δ(...
0
votes
0answers
57 views
Converting Turing machine into the source code in industrial programming language?
Are there methods how to convert Turing machine (e.g. neural Turing machine or other rigorous Turing machine) into the source code/program that is written in some industrial programming language like ...
1
vote
1answer
13 views
Doubt in definition of closure under concatenation operation in Recursive Enumerative languages
I recently started studying theory of computation.
Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.
Please Note - RE shortform i am ...
0
votes
1answer
34 views
Number of Configurations of LBA(Linear Bounded Automaton)
The lemma is:
Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet.
There are exactly $qng^n$ distinct configurations of $M$ for a tape of
length $n$.
I want know why LBA has ...
0
votes
0answers
22 views
How to measure the length of the program on Turing Machine?
In Kolmogorov complexity, there is a notion: length of the shortest program that describes the data. I can use Lempel-Ziv compression to estimate this value. What if I want to estimate this value by ...
0
votes
0answers
31 views
A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$
I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ ...
1
vote
0answers
18 views
Deterministic Time Hierachy Proof by Arora and Barak: Question about time to simulate Turing Machine $M$ that decides separating language
In the book "Computational Complexity: A modern approach", Arora and Barak proof the statement that $DTIME(n) \subsetneq DTIME(n^{1.5})$ by constructing a separating language $L \in DTIME(n^{1.5})$ ...
2
votes
0answers
48 views
On teaching Kolmogorov complexity with Python and the complexity of composed strings
The setting of this question is a bit long-winded, but please bear with me.
This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
0
votes
0answers
18 views
Why are CFL not closed under set difference, and complementation? [duplicate]
I was wondering why CFL are not closed under set difference, and complementation can anyone explain? I tried searching, but no luck.
1
vote
1answer
45 views
What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?
I am confused about Turing Machines that are able to decide languages that contain infinite words.
Are languages with an infinite amount of only finite strings always decidable?
How can a Turing ...
0
votes
1answer
23 views
Proving whether an input sequence is in a given RE language
I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this ...
