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

learn more… | top users | synonyms

2
votes
0answers
23 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? The usual algorithms rely on indirect access, so how much does losing it cost us? Say we have $N$ integers from $[0, 2^B)$. It's not ...
-1
votes
0answers
39 views

Solvable & Unsolvable Problem Detection [duplicate]

be aware that this problem dosnt have solution. I ran into A multiple choice question on previous midterm on Computation Theory course. this question is which of the following problem is not ...
-5
votes
0answers
64 views

Unsolvable Problem Question [closed]

I Ask this question on Math Section, but the users encourage me to ask it here. The halting problem is the most famous of all unsolvable problems. i try to summarize one list of unsolvable problem. i ...
2
votes
0answers
73 views

Prove that turing machines and the lambda calculus are equivalent

It is known that a turing machine and the lambda calculus are equivalent in power. I now want to try to prove this myself. I think proving that the lambda calculus is at least as powerful as a turing ...
0
votes
1answer
27 views

Intersection and partial quantity decidability [closed]

I'm still insecure in the section decidability (no proof needed, I want to divine it): X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable? X is decidable ...
2
votes
3answers
96 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
0
votes
1answer
51 views

Describe a TM through denotation of the transition function

I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language $$ L ={\{w\#w} \mid w \in {\{0,1}\}^*\} $$ over the input alphabet: $$ ...
4
votes
2answers
95 views

Are Boolean functions Turing complete

A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$. The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left ...
0
votes
0answers
42 views

How to simulate a cellular automaton via a Turing machine

It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by ...
19
votes
6answers
838 views

Is there a connection between the halting problem and thermodynamic entropy?

Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem. A TM is an abstract concept of a machine (or engine if ...
0
votes
1answer
37 views

Confusion in Reducibility

In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM We let R be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following ...
1
vote
2answers
69 views

Having trouble with turing machine over language $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$

I am having trouble giving the description of a Turing machine that goes for $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$. What I have so far is: If we start with a blank, the string is empty and it ...
0
votes
1answer
45 views
1
vote
1answer
71 views

Turing Decidable [closed]

M = (Q, Σ, Γ, δ, q1, qaccept, qreject), where Q ={q1, q2, qaccept, qreject}, Σ = {0, 1}, Γ = {0, 1, U}, and transition function δ is as follows: ...
1
vote
0answers
20 views

Undecidability instance on a “find a proof/disproof” machine

I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on: Suppose we built the ...
0
votes
0answers
41 views

Can we recognize wheter a Turing machine is a decider?

Let $L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$. Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor ...
5
votes
2answers
693 views

Can we represent all computer programs as graphs?

I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an ...
1
vote
2answers
45 views

Proving a language is not decideable using a reduction from Busy Beaver?

I was given this function: $F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural ...
4
votes
1answer
152 views

Turing-unrecognizable language - what TM does?

I have a problem giving "intuitive" explanation to turing-unrecognizable languages. We can prove that, say, ${\overline{A_{TM}}}$ is not turing-recognizable, because that would make ${{A_{TM}}}$ ...
2
votes
1answer
95 views

Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
4
votes
1answer
68 views

Relation between RAM and Turing machine

Denote $D$ a set of finite sequences of integers. In Papadimitriou's "Computational Complexity" in theorem 2.5 it is proved that if a RAM program $\Pi$ computes a function $\phi$ from $D$ to integers ...
0
votes
1answer
100 views

What would show a human mind is/is not reducible to a Turing machine?

In computer science it is often assumed that a human mind can be reduced to a Turing machine. This is the assumption that underlies the field of artificial intelligence. However, it is an ...
1
vote
1answer
97 views

Inclusion of complexity classes (Deterministic Turing Machine)

I can't understand what my professor wrote about these inclusions concerning deterministic classes: $$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$ I understood ...
1
vote
1answer
57 views

Turing machine with repeated strings

How would I go about making a Turing machine to accept the following language L? $$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$ I was thinking counting the number of symbols in the input ...
0
votes
0answers
16 views

Does the head of TM M ever move into cell x when processing Input I?

The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive. Is it decidable whether a TM reaches some position ...
3
votes
1answer
90 views

Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete? The set ...
0
votes
1answer
32 views

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

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
21 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
147 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
27 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
24 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
2answers
64 views

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

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... ...
6
votes
2answers
78 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
143 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
67 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
83 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
32 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
39 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
131 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
483 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
94 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
76 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
884 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
62 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 ...
5
votes
2answers
282 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
32 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
81 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$ ? ...
4
votes
1answer
137 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
89 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?
2
votes
1answer
94 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 ...