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

learn more… | top users | synonyms

0
votes
1answer
27 views

Maximum number of configurations on a TM that decides the language $A_\text{NFA}$ [on hold]

Consider a Turing Machine $M$ that decides the following language: $$A_{\text{NFA}} = \{ \langle N,w \rangle | N\text{ is an NFA and }N\text{ accepts }w \}.$$ Based on its input size, if $M$ wants to ...
1
vote
1answer
15 views

Alternate definitions of enumeration machines

In my textbook, enumeration machines are defined as possessing a special write-only output tape, which they can write characters to, but not move the head of. When they hit the print state, the string ...
4
votes
3answers
112 views

Can a Multi-Tape Turing Machine have an infinite number of tapes?

So if k is the number of tapes, is a multi-tape Turing machine allowed to have k = ∞ tapes. I'd assume not since this would give an infinite transition function?
0
votes
1answer
23 views

Deterministic Multi-tape Turing Machine construction

I'm trying to construct a deterministic multi-tape turing machine for the following language in order to show that $L$ is in $DTIME(n)$: $$L = \{ www \mid w \in \{a,b\}^+ \}$$ I'm not sure how to ...
0
votes
1answer
18 views

can a post machine have more than one accepting state?

I was searching through google and I couldn't find anything Can a post machine have more than one accepting state ? Yes or No ?
0
votes
0answers
16 views

URM simulate TMs/TMs simulate URM [closed]

Theorem: partial function is only computable by a Unlimited Register Machine iff it is computable by a standard TM How to prove this theorem? Maybe simulate these two machines in both way? Can ...
0
votes
2answers
46 views

How to find out what are accept, loop and reject in this Turing Machine?

I am trying to find out accept, loop and reject in this Turing Machine because it doesnt have any...I am not sure if I completely understand it but this is the turing machine I am talking about... ...
3
votes
1answer
34 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
2
votes
2answers
83 views

Intersection/Union of recursively enumerable languages that aren't decidable?

For $L_1, L_2 $ and $L_1 \in RE $ and $ L_1\notin R$ and $L_2 \in RE $ and $ L_2\notin R$ I was asked to prove/disprove if the following can occur: $L_1 \cap L_2 \in R$ $L_1 \cup L_2 \in R$ $L_1 ...
2
votes
2answers
49 views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
0
votes
1answer
76 views

What is the formal description of a Turing machine?

I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what "formal description" entails.
1
vote
1answer
22 views

How do you prove that this TM decides a language that is undecidable? [closed]

In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language $$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w ...
0
votes
0answers
38 views

Parsing Turing Machine

Have a question that requires me to write the rules for parsing a turing machine This is the question The PROBLEM involves writing a set of Turing Machine rules that will read and determine whether ...
1
vote
2answers
118 views

Can a Turing Machine have fewer states?

I am currently learning about Turing Machines, I am curious if a Turing Machine can have fewer states ? Can it be done like a Transition Graph where you can have multiple states at once ? I got ...
4
votes
1answer
378 views

how to draw a complement of a Turing Machine?

I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite ...
1
vote
2answers
81 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
0
votes
1answer
36 views

Turing machines and languages — recursive (enumerable) or not

For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could ...
10
votes
1answer
855 views

Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?

In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also ...
1
vote
1answer
46 views

Is the language of TMs that halt on some string recognizable?

I would like to show that the following language is recognizable: $$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$ How do I go about showing that this language is ...
4
votes
2answers
183 views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
-2
votes
1answer
24 views

Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
-1
votes
2answers
69 views

Tricky Turing Machine state diagram

what would the Turing machine state diagram be for this language: $A=\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\} $ ? how would the turing machine design know the size of $(1 \cup 2)^b$ ? ...
-1
votes
0answers
36 views

Turing-Machine that does not accept any string [duplicate]

Here's the question:"Give an example of an infinite decidable set L where L ⊆ {M | M is a Turing machine that does not accept any string}" Does this means L is also a TM that does not accept any ...
4
votes
1answer
89 views

Turing machine - infinite tape in one or two directions

I have seen turing machines beeing represented with tapes infinite in one, and in two directions. Is there any difference in the power of such turing machines, or are they basically equivalent? In my ...
0
votes
1answer
63 views

how do I find a undecidable subset of a set that's decidable? [closed]

Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?
1
vote
0answers
58 views

How to Study Space Complexity

I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially ...
2
votes
1answer
36 views

Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?

Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine ...
1
vote
1answer
74 views

Can Turing Machines decide on computability? [closed]

Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?
4
votes
2answers
47 views

Does an enumerator print the first occurrence of a word in finite time?

For a proof I need to use the fact that every word in the language of an enumerator occur on the output paper in finite time. Is it true? For example, the language of the natural numbers in decimal ...
1
vote
1answer
28 views

ALL_{REGEX} in PSPACE algorithm

$ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$. In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ ...
1
vote
1answer
53 views

Regarding Turing Machine Halting Problem [closed]

All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting ...
3
votes
1answer
53 views

What is the difference between RAM and TM

In case of algorithm analysis we assume a generic one processor Random Access Machine(RAM). As I know RAM is machine which is no more efficient than the Turing machine.All algorithms can be ...
3
votes
1answer
123 views

How turing machine can be used as enumerator

Currently I am studying Turing machines and I understand that a Turing machine can produce all the strings of the language accepted by that particular Turing machine. We call such a Turing machine an ...
5
votes
2answers
68 views

Regarding the Turing Machine

I am a high school student in the twelfth grade. I study high-level programming, and a little bit of basic computer science. I have recently started to understand what a Turing Machine is. I wanted ...
2
votes
2answers
50 views

Understanding decidability

Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course. 1) I am reading why the language AFDA is decidable ...
2
votes
1answer
37 views

A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
2
votes
1answer
42 views

How do you classify properties as Trivial and Non-trivial? [duplicate]

I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone ...
2
votes
0answers
55 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
1
vote
1answer
96 views

If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?

If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?
-2
votes
3answers
75 views

Is human being a Turing Machine?

We may not have a determinate answer to this question. But is there any evidence for or against this question? Or is there any study on it?
3
votes
2answers
43 views

How to write a many-one reduction proof

Writing a proof by contradiction is fairly formulaic--first you assume the opposite, then derive a contradiction. I would like to know the steps and conventions for writing a many-one reduction ...
1
vote
1answer
31 views

Logspace Transducer

I know that a logspace transducer is a deterministic Turing machine that enables us to use log-space complexity. I do not understand though why that is correct. Whatever algorithms can be implemented ...
2
votes
0answers
145 views

Difference between deterministic and nondeterministic universal turing machine

It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a ...
2
votes
1answer
41 views

CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
4
votes
3answers
232 views

Why can't we flip the answer of a NDTM efficiently?

I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) ...
0
votes
1answer
55 views

Decidability Problem [closed]

given a turing machine M over the input alphabet $\Sigma $ , any state q of M and a word w $\epsilon\Sigma $* , does the computation of M on w visit the state q ? Is this problem decidable ?
1
vote
2answers
47 views

Prove Queue Automaton is equivalent to Turing Machine

A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end. ...
2
votes
2answers
114 views

Proving iff statement with reductions

I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages. Question: Let $ A = \{ ww \ | \ w \ \epsilon \ ...
1
vote
1answer
87 views

Reduction to complement of Accept Problem

I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M \text{ is TM}, w \not\in L(M) \}$$ To this Turing ...
1
vote
0answers
65 views

Understanding a Turing machine description

My professor has been going over Turing machines, and I really don't understand how this example of a Turing machine for binary addition has to be read: I love working with finite state machines; ...