# Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

1,923 questions
Filter by
Sorted by
Tagged with
26 views

### Is pushdown automata with infinite language decidable and why?

I have following problem: INFINITEPDA={⟨A⟩ |A is pushdown automata and L(A) is its infinite language} Prove that this is decidable problem. So my idea how to ...
13 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 ...
11 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
51 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 ...
52 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 ...
31 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$ ...
84 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 ...
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 ...
60 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 ...
32 views

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 ...
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 ...
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). ...
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, ...
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 ...
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 ...
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 ...
34 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 ...
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 ...
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?
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 ...
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. ...
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.
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 ...
106 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 ...
58 views

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 ...
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 ...
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 ...
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 ...
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 ...
48 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 ...
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 ...
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 \...