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

learn more… | top users | synonyms

-1
votes
1answer
28 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
1answer
14 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
84 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
79 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
27 views

Complement of $\{\langle M\rangle\mid M \text{ enters state q5 for the input string } 101\}$

Let language $L_1 = \{\langle M\rangle\mid M \text{ enters state q5 for the input string }101\}$. Would the complement of the language $L_1$ be $$\{M \text{ does not enter the state q5 for the ...
3
votes
0answers
56 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 - ...
-2
votes
0answers
57 views

Show that the language of words that polynomially bound accepting inputs of a TM is in NP

I am doing the exercise 2.1 in the book "Computational Complexity: A modern approach" by Sanjeev Arora and Boaz Barak. Prove that allowing the certificate to be of size at most $p(|x|)$ (rather ...
1
vote
1answer
26 views

How to prove strict space lower bounds using crossing sequences in Turing machines?

I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems? For example, suppose that you ...
1
vote
1answer
45 views

Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine [closed]

The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part ...
1
vote
0answers
61 views

K -> 2 tape reduction for nondeterministic Turing machines

How to I show that any language in NTIME(T(n)) can be accepted by a non-deterministic 2-tape O(T(n)) time-bounded Turing machine, with modifiable input tape? I've seen the k to 2 tape reduction for ...
10
votes
1answer
539 views

What does sublinear space mean for Turing machines?

The problem of deciding whether an input is a palindrome or not has been proved to require $\Omega(\log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn't ...
3
votes
1answer
70 views

Lower space bound on a turing machine accepting palindromes

Let $$ PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace $$ How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$? I have a feeling that I need to use ...
0
votes
2answers
53 views

Decidability of empty intersection of two languages accepted by Turing machines

I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not. I have a language $\qquad\displaystyle L = \{ (R(M_1), R(M_2)) ...
0
votes
2answers
74 views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...
3
votes
2answers
89 views

Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?

In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in ...
-1
votes
2answers
79 views

Extension of Rice's theorem

How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is ...
2
votes
1answer
39 views

How is Rice's theorem applicable to this decision problem?

I recently had a test in introduction to computability and I got the following question wrong. The question Input: A classical Turing machine $M$ with a 2-dimensional tape. output: Does there ...
3
votes
2answers
68 views

Does “output” always imply halting in computability?

$L = \{P : P(n)$ outputs $n^2$ for all $n \in N \}$ In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can ...
-1
votes
2answers
56 views

Strange TM Language on Definition [closed]

i prepare for Autotmata Course Final Exam. in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote: Language of this TM is: {$W \in ...
-2
votes
1answer
15 views

$L \in RE$ Question [closed]

I see a sentence in one final exam on automaton course. I have one problem: if we want to have a TM that halts for all word in L, it's enough to have L be R.E? or we should have R be R.E and ...
0
votes
1answer
43 views

Connection of “modern” runtimes and number of steps on a Turing machine

Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is ...
1
vote
0answers
46 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM ...
2
votes
0answers
38 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 ...
2
votes
0answers
90 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
28 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
124 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 ...
2
votes
1answer
74 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
109 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
48 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
894 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
41 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
75 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
47 views
1
vote
1answer
80 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
32 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
46 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
718 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
46 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 ...
5
votes
1answer
178 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
125 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
78 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
108 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
102 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
68 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
18 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
95 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
33 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
24 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
161 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
41 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 ...