Tagged Questions

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

learn more… | top users | synonyms

1
vote
1answer
45 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 ...
5
votes
4answers
606 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
35 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
32 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
19 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
30 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? ...
-2
votes
0answers
23 views

Draw out TM where 1<=n<=|w| the nth character from the left is equal to the nth character from right

We need to write TM for strings over {a,b,c} for some n, 1<=n<=|w| the nth character from the left is equal to the nth character from right. Can someone help me understand the meaning and how ...
-2
votes
1answer
62 views

prove 3x+1 problem is undecidable [closed]

Let f(x) = 3x + 1 if x is odd, or f(x) = x/2 if x is even. if you start with an integer x and iterate f, you obtain a sequence x, f(x), f(f(x)), …, stop if you ever hit 1. For example, if x =17, ...
4
votes
1answer
44 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
35 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
15 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
87 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
82 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
28 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
57 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 - ...
1
vote
1answer
29 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
46 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
64 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
543 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
75 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
55 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
77 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
80 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
69 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
16 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
43 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
91 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 ...
3
votes
3answers
144 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
115 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
58 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
896 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
42 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
83 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
49 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
721 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
192 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
130 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
85 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
109 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 ...