Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
71 views

Doubt regarding Cantor's diagonalization argument [closed]

So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider. I understand the overall argument but have a problem regarding one caveat mentioned in my ...
1
vote
1answer
32 views

Simulations between Turing machines

I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the ...
5
votes
2answers
110 views

motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
1
vote
2answers
398 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
30 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?
0
votes
1answer
62 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
65 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
93 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
227 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 ...
1
vote
1answer
562 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. ...
0
votes
2answers
78 views

Turing machine that applies homomorphism on input string

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 ...
2
votes
0answers
20 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 ...
0
votes
1answer
79 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
42 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
67 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
73 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
32 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
112 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
354 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
36 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
46 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
178 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
17 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
990 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
42 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\...
6
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
107 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
63 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
74 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
231 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
94 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
59 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
68 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
20 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
48 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
60 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
341 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
83 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
303 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
207 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
90 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
37 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
119 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
55 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
35 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
20 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
133 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
23 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
85 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 ...

1
3 4
5
6 7
37