Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
1,922
questions
1
vote
1answer
7 views
Infinite recognizable not decidable subsets
If L is an infinite ($|L|=|\mathbb{N}| $) decidable language, prove that it contains:
a) An infinite subset that is not recognizable
B) An infinite subset that is recognizable and not decidable
For ...
0
votes
0answers
9 views
a pushdown automaton, which accepts the following language: [closed]
i have problem solving this problem i know how to make the second part of it the form but
the first part that number of a+b =c+1 i didn't catch it yet anyone please can help me and thanks
1
vote
1answer
50 views
Are there more Turing-unrecognizable languages than recognizable?
Say you generated a language by looking at the output of a lexicographic enumerator and flipping a coin for each string, adding it to the language on heads. What would be the chance of this language ...
0
votes
0answers
39 views
Halting problem. Decider “recognising itself” in the input?
This is about the halting problem. My questions are: where do you think are logical flaws in what I am going to write? How do you think this does not invalidate the proof for the undecidability of the ...
1
vote
1answer
30 views
A property of Kolmogorov random strings
I am working on the following problem:
Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\{0,1\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ ...
2
votes
2answers
79 views
how does Kleene-Post show two languages that are not Turing reducible to each other?
I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument.
I've seen ...
3
votes
0answers
26 views
Can any computably enumerable set be generated by a prefix-free set?
Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the ...
1
vote
2answers
58 views
Why do we proof the halting problem with turing machines?
It can be shown that Turing machines, μ-recursive functions and reasonable programming languages can compute/decide the same problems. I wonder why we then still proof the halting problem with Turing ...
0
votes
1answer
32 views
Functional Abbreviation for Inst Expression in Turing's 1936 Paper
In Turing's 1936 paper On Computable Numbers Page 30-31, and its Correction Page 1-2 :
For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l ) $ means that if $M$ scans symbol $S_j $ under $m-...
0
votes
1answer
19 views
Recognizability and complements
I'm learning about Turing Machines, decidability, and recognizability, and read that if a language is recognizable, its complement is sometimes recognizable. I don't really understand how this could ...
0
votes
1answer
18 views
If two languages are decidable, can one be mapping reducible to the other?
If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
0
votes
0answers
15 views
Unrecognizability and Decidability [closed]
I'm learning about Turing Machines and decidability and had a question and am looking for some guidance on how to go about solving it.
Prove that if a language L is unrecognizable, then L is always ...
0
votes
0answers
20 views
Is there a decision problem in NP whose corresponding function problem is not in #P?
I am trying to get an imagination of the class #P for my bachelor thesis. Right now I think of it as a DTM that runs every possible path to run an algorithm on some decision problem at once. But in ...
2
votes
1answer
120 views
Proof of universality in the circuit model
I'm starting to study Turing machines, the Church-Turing conjecture and the circuit model. In particular, I'm interested in the proofs of universality that one can find in this context. So far, I have ...
0
votes
0answers
35 views
How would I prove that nondeterministic Turing machines are undecidable?
How would I go about proving that the language:
$$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$
is undecidable?
I looked at the proof for $A_{TM}$ ...
0
votes
0answers
15 views
Multiple loops in a Turing Machine?
Consider a Turing Machine which (1) reads all its input and (2) accepts inputs arbitrarily large. Given the affirmative answer to the previous question that there must be a loop in the finite-state ...
3
votes
0answers
63 views
is it decidable whether a grammar in Chomsky normal form has useless rules?
Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
4
votes
1answer
281 views
Undecidability of “is this CFG prefix-free?”
I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).
Another thread has the very different question "...
1
vote
0answers
24 views
Mathematical Symbol
I remember about 10+ years ago there was a mathematical symbol used to represent population sustainability.
It resembled a downward or upward angled arrow but in dot form...if remember it was ...
-1
votes
1answer
24 views
What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?
I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
-1
votes
0answers
30 views
Machine that recognizes more than countable languages - is it superturing (doing hypercomputation)?
I am reading thesis http://dspace.lu.lv/dspace/bitstream/handle/7/48857/298-71916-Dimitrijevs_Maksims_md09032.pdf?sequence=1 which says:
Abstract Turing machines can recognize countably many ...
0
votes
1answer
30 views
Does CSL contain an empty string or not? Is empty string accepted by LBA or not?
I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite ...
0
votes
1answer
39 views
Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$
I need to find a Turing machine that decides $A=\{0^{3^n} | n\ge 0\}$.
I tried doing the same as Sipser does on page 172 in his back, where he creates a Turing machines that decides $A=\{0^{2^n} | n\...
1
vote
2answers
34 views
Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine?
Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get ...
5
votes
2answers
1k views
What are the options of head movement for a Turing machine?
I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is ...
0
votes
0answers
36 views
Prove for the theorem “Every non deterministic Turing maching has an equivalent deterministic Turing machine”
I know that a Deterministic TM single tape has an equivalent Deterministic TM multiple tape, but I can't get how a Deterministic TM multiple tape can simulate a non-deterministic TM(The mecanisme).
...
1
vote
1answer
95 views
What does “lookahead” refer to?
I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word.
What does "lookahead" refer to? How does this relate to LL, ...
1
vote
0answers
42 views
How to add two positive or negative integers using the same Turing Machine
I want two know how can I add two positive or negative integers using the same Turing Machine
I am using unary numbers in the following way:
0 = 1; 1 = 11; 2 = 111; 3 = 1111 ...
I know how to add two ...
1
vote
2answers
36 views
How are useless states created NFA to DFA
So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA ...
1
vote
0answers
25 views
A genral Turing model with one tape to define sublinear space (L,NL,..)
A genral Turing model with one tape to define sublinear space (L,NL,..)
Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
1
vote
2answers
33 views
Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?
What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages?
I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and ...
1
vote
1answer
24 views
Proof that languages are Turing-recognizable iff computably-enumerable
A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.
In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
0
votes
1answer
28 views
Incomputable sets of low degree vs Rices theorem?
I have heard that there are sets that are not computable, but are lower in degree than the halting problem.
How does this not contradict Rice's theorem? Are there any concrete examples of such sets?
0
votes
1answer
26 views
How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs?
Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs?
By a Halt1 oracle I mean that we have the ability to decide if Turing ...
0
votes
1answer
55 views
Halting problem for turing machines with one input
My question is:
Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs.
...
0
votes
0answers
34 views
Turing machine M' from M
Let M be a Turing machine not necessarily halting on every input. Construct Turing machine M′ which halts on w if ww ∈ L(M) and does not halt otherwise.
1
vote
0answers
43 views
Blank symbol on output tape
A unary Turing Machine X has input alphabet Σ and tape alphabet Γ. We represent the blank symbol belonging to the tape alphabet as _ . Given as input 11111 X writes 1_1_11_1 as output.
Is the blank ...
0
votes
3answers
105 views
What are analog and digital in computer science?
I once thought that any analog computer is any computer which "doesn't need electrical current to work".
I once thought that any digital computer is any computer which "does indeed need ...
1
vote
1answer
58 views
Cannot understand reductions from the halting problem and its complement
When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt ...
3
votes
1answer
88 views
Disprove unrealistic speed-up of total Turing machines
Let $T_1$ be a total Turing machine deciding language $L_1$, and let $I_1$ and $I_2$ be two separate inputs to $T_1$. Further, let $I_{c}$ be $I_2$ concatenated to $I_1$ with some separation symbol in ...
-1
votes
1answer
65 views
Is this Language decidable?
As the title says;
is this language decidable and how do you prove it?
$$L =\{\langle M\rangle \mid M \text{ is a Turing Machine and there is an input that } M \text{ halts on} \} $$
1
vote
1answer
76 views
Church–Turing thesis and infinite Turing machines
What exactly is the definition of church turing thesis? It's really confusing.
I want to prove the following statement:
A Turing machine with infinitely many states is more powerful than a regular ...
1
vote
0answers
26 views
Understanding the equivalence of a Turing machine and an enumerating machine
The normal argument for a decidable language to build an enumerating machine is given as follows:
Let $M$ be a Turing machine which decides a language $L$, and let $s_1,s_2,\ldots$ be a list of all ...
0
votes
0answers
14 views
Building an enumerating machine with a Turing machine
I have a Turing machine say M with a state diagram which decides a particular language...
I wanted to build an enumerating machine for the same..
Since its decidable..
I can use the following logic
...
0
votes
0answers
65 views
what is the function of a turing machine
The main question asked me to build a certain turing machine such that given a word w over {0,1}*
the turing machine accepts all such words and ends in accept state with the tape string = the word ...
0
votes
1answer
81 views
Computational power of a Turing Machine with infinite states
Consider a turing machine with infinite states. This machine is identical to a regular machine. Only that number of states could be infinite.
Does this machine has more computational power than a ...
-1
votes
1answer
47 views
Does the set ALL_TM contain all Turing Machines?
ALL_TM = { TM | A valid TM }
This was a question on my exam.
As my choice of answer I went with yes, since the set of all Turing Machines is countable, ( you can produce a binary string for each and ...
0
votes
1answer
41 views
Universal Turing Machine algorithm
First, I learned this based on these facts:
Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$.
Any computation rules that can use to simulate any possible ...
0
votes
1answer
83 views
Algorithmic problem of regular, context-free, and recursively enumerable languages
Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free.
Are the following problems algorithmically decidable?
Is $L_1 \cap L_2 = L_3$?
Is $L_1 \...
-2
votes
1answer
46 views
running RAM on a given input
I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance,
there's a Random Access Machine which has an input {0,1}*. The ...
