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

learn more… | top users | synonyms

1
vote
1answer
20 views

Are all languages generate by Turing machines countable?

Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?
1
vote
2answers
43 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
-2
votes
1answer
20 views

How can I construct a Turing Machine that accepts encoding of another Turing Machine? [closed]

How can I construct a Turing Machine that accepts the language L = <'M'> which is an encoding of a Turing Machine M?
0
votes
1answer
25 views

Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is ...
3
votes
1answer
30 views

Turing machine working only with 1's and blanks - how to encode input?

Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input? My ...
5
votes
1answer
204 views

How a reduction can help up solve a problem?

I am studying the basics of Computation Theory and I came up with an example I can't understand. Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of ...
4
votes
6answers
1k views

How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
1
vote
1answer
46 views

Turing Machine for strings without bbb

I am trying to generate a transition graph for a turing machine that accepts the languages of all strings that do not contain the substring $bbb$ with the input alphabet $\Sigma = \{a, b\}$. When I ...
0
votes
0answers
25 views

Is it decidable whether a TM accepts more than one word?

Is the following language: $\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$ Turing-decidable? I think it isn't, because if a Turing machine T can ...
2
votes
2answers
69 views

How to construct a turing machine for a language

I have proved that language $L$ is not regular and think that it is recognizable by a Turing machine. I want to prove it by constructing a Turing machine for it. $L=\{0^n|n \in A\}$ where $A$ is ...
12
votes
6answers
3k views

Is there a physical analogy to the Turing Machine?

Recently in my CS class I've been introduced to the Turing Machine. After the class, I spent over 2 hours trying to figure out what is the relationship between a tape and a machine. I was ...
-1
votes
0answers
17 views

Problem constructing a Turing Machine

I need to construct a Turing Machine that accepts the language L={ a^n b^2n | n >=1}. I am not sure how to go on about the part where the Turing Machine will ...
1
vote
1answer
29 views

Recovering the transition function of a Turing machine with a known number of states

Suppose we have a Turing Machine and know how many states it has as well as bound on its running time, but do not initially know its transition function. Is it possible to determine its transition ...
1
vote
1answer
24 views

Constructing a deterministic one way infinite single tape Turing machine

If I have an input string that is only composed of $a$'s and $b$'s, how can I construct a Turing machine that only accepts strings where the number of $b$'s divides the number of $a$'s? For example: ...
1
vote
1answer
184 views

Show there exists a turing machine with the following properties

I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the ...
2
votes
2answers
467 views

Turing Machine Decidable: What right does the definition have to say what's not in language L?

I'm having trouble understanding the definition of Turing Decidable. The definition goes something like this: TM M decides language L iff the strings in L put M into the Accept state and the ...
1
vote
1answer
58 views

Can a solvable problem be encoded in a recursively enumerable language?

Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new ...
3
votes
4answers
713 views

What is the point of finite automata?

Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?
2
votes
1answer
111 views

Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN}

Having trouble with this homework problem. In order to show that A is Turing recognizable and decidable. $\text{EVEN} = \text{binary strings with even length}$ $Let\;A = \{(M) | \,M\; \text{is a DFA ...
-1
votes
1answer
29 views

Why apply the assumed decide für HALT to the input and its code?

In the lecture notes I have got in class I have the following proof for the halting problem not being recursive Assume $H$ is recursive and TM $M_1$ decides it. Construct $M_2$ that gets ...
2
votes
1answer
29 views

Multitape Turing machine with multiple non-blank tapes

A multitape Turing machine is defined to have input only appear on one tape, with the rest of the tapes blank. Are there any formulations of a Turing machine that allow other tapes to be not blank? ...
2
votes
1answer
25 views

“Print 'em all game” for Turing machines

Suppose that we have a tape restricted to $n$ cells on binaryalphabet $\Sigma = \{0,1\}$ and initially filled with zeroes. We want to build a Turing machine $M_n$ (or better a Linear Bounded ...
0
votes
2answers
58 views

Is emptiness of the intersection of the languages of two TMs decidable? [duplicate]

Let $\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$. How do I know if this language is decidable or not? And How do I prove ...
0
votes
1answer
18 views

Definition of Turing machines and rejection states

In some definitions of Turing machine, there is only a set of accepting states and no mention of a set of rejecting states. But it seems to me that the definition that includes only a set of ...
0
votes
3answers
53 views

Where does the need for conditionals (if, switch, jump tables, etc…) truly arise? [duplicate]

I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind. When we ...
2
votes
0answers
17 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} ...
1
vote
1answer
47 views

Turing-recognizable languages closed under star operation

I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a ...
1
vote
2answers
27 views

Is it necessary to traverse every letter in the tape of a Turing Machine?

Say I want to make a very simple Turing Machine that accepts only strings that contain one or more a's. Can I simply send have the machine move a HALT state once it reads one a, even if there are many ...
3
votes
1answer
45 views

The language of any constant-time Turing machine is regular

Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular. This seems to be a ...
-1
votes
1answer
114 views

Proving equivelance of a multijump turing machine and a turing machine

I'm having trouble getting started on this proof, and I was hoping you guys could give me a couple hints/point me in the direction of where to start? Here's the problem: Consider a multijump Turing ...
0
votes
0answers
10 views

Are there any recent results regarding Busy Beavers?

It appears there is a lot less research on this subject than around 20 years ago. I was able to find only a few new results (most prominently those displayed by Georgi Georgiev). Did I completely ...
0
votes
1answer
48 views

Simulate a regular Turing Machine with one that cannot write blanks

Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?
1
vote
1answer
17 views

Can we obtain a state diagram of a single Turing machine

When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different ...
2
votes
2answers
59 views

How is the number of states in a Turing machine bounded?

The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not ...
0
votes
1answer
17 views

Why are macro tapes bidirectional?

A k-macro Turing machine uses a tape which is split in blocks of k cells and works on all of them directly. After work, the head can end just beside either the right or the left end of such a block. ...
5
votes
1answer
216 views

Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
1
vote
2answers
42 views

What is the set of operations of a Turing machine?

From https://en.wikipedia.org/wiki/Abstract_machine A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former ...
3
votes
2answers
164 views

Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape ...
1
vote
1answer
58 views

Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
6
votes
6answers
764 views

Do turing machines assume something infinite at some point?

In a previous question What exactly is an algorithm? , i asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm. One of the ...
0
votes
2answers
47 views

Help designing a Turing Machine

I am faced with the following question: Design a Turing Machine that recognizes the language $L = \{1^{2n+1}\mid n \text{ is a non-negative integer}\}$. Show the state diagram. I started doing ...
-3
votes
1answer
38 views

The meaning of $*$ in regular expressions

I'm designing a Turing machine that decides a language denoted by a regular expression. Let's say this expression is $a^*bbc^*$. Does this machine accept the string $bb$ since $a^*$ and $c^*$ can have ...
-2
votes
1answer
34 views

Can every recursively enumerable language be defined with regular expression?

Can every recursively enumerable language be defined with regular expression? I came across this question, when studying for my test: Prove that for any finite language $L$, there is a Turing machine ...
2
votes
1answer
31 views

Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)

Is this problem decidable? Given two representations of Turing machines $R(M_1), R(M_2)$, is the length of the computation of $M_1$ longer than the length of the computation of $M_2$ on every input? ...
4
votes
1answer
55 views

Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. ...
-1
votes
1answer
50 views

Proof that L(M) = {accepts the string 1100 } is undecidable

Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$ To proof that the language $L$ is undecidable I should reduce something to $L$, right? I tried ...
0
votes
0answers
27 views

Simulating two dimensional tape TM with ordinary two tape TM

So I know that any multiple tape Turing Machine can be simulated with the one tape TM. But what about if we have a two dimensional tape TM? Can it be simulated with the ordinary two tape TM? Will they ...
0
votes
1answer
94 views

Decidability of a language of Turing Machine descriptions [duplicate]

Given the language $\{ <M> \mid\:$ M is a Turing machine and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions$\}$ How can one prove that this ...
3
votes
1answer
116 views

Non-deterministic Turing machine and palindromes

I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$. I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – ...
3
votes
0answers
61 views

Problems that provably require quadratic time

I'm looking for examples of problem which has a lower bound of $\Omega(|x|^2$) for input $x$. The problem needs to have the following properties: $\Omega(n^2)$ runtime proof for any algorithm - ...