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

learn more… | top users | synonyms

1
vote
1answer
10 views

Equivalence in finite sets of turing machines

I have this exercise and I really don't know how to complete it: ...
2
votes
3answers
165 views

Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case. EDIT If it can be reduced to Halting problem, then how? ...
1
vote
2answers
39 views

What's the error in the following proof of the halting problem decidability?

Let's encode every state and tape word (with position of Turing machine on it) with a single integer. Then the transition function can be represented as a total function from integers to themselves. ...
5
votes
2answers
134 views

Why is the tape not part of the definition of a Turing Machine?

I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine. Consider, for example, the formal definition of a Turing machine on Wikipedia page. The definition, ...
1
vote
1answer
53 views

Problem in Papadimitriou's “Computational Complexity” seems odd

I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition. On page 66, we have: 3.4.1. Problem: For each of the following problems involving ...
0
votes
1answer
42 views

Decidable language: set of context-free langauges containing 1 string

ONE = {(G) : G is a CFG such that L(G) contains exactly one string} . I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input. I am struggling at ...
2
votes
3answers
61 views

Reduction from $L_{nonuniversal}$ to $L_{finite}$

As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly. Given are two languages $L_{finite}$ and ...
-3
votes
1answer
40 views

Is $H_0$ reducible to $\overline H_0$?

Be $H_0$ the special halting problem with $$H_0 = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace^* | \varepsilon \in L(M)\rbrace$$ and $\overline{H_0}$ being its complement. Is $H_0$ reducible to ...
1
vote
1answer
33 views

How to turing reduce equivalent languages $Q$ to infinite language $I$

Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$ I'm trying to Turing reduce $Q$ to $I$ ...
2
votes
1answer
68 views

Proof by Turing Reduction

I need to proof the following by turing reduction. Given two languages: $Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$ $I= \{\langle M \rangle \mid \;\vert L(M) \vert = ...
-1
votes
1answer
34 views

Turing machine that accepts when a string of x's is followed by the same number of y's

I need to draw a machine's states that accepts (writes a 1) when it reads a string of x's that is followed by the same number of y's and would reject (writes a 0) for anything else. It has to work for ...
9
votes
5answers
3k views

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
1
vote
0answers
24 views

How does one calculate the block-sensitivity of a function?

I am looking at this paper : http://arxiv.org/pdf/1411.3419v1.pdf But somehow I am not being able to fish out a method to calculate this quantity called the "block-sensitivity". Can someone kindly ...
-2
votes
1answer
48 views

Two Disjoint Turing-recognizable languages do not have a decidable language

Let languages $A, B$ be defined as $$\begin{align} A &= \{\langle M\rangle\mid M(\langle M\rangle)=reject\}\\ B &= \{\langle M\rangle\mid M(\langle M\rangle)=accept\} \end{align}$$ In other ...
0
votes
1answer
40 views

Showing that the set of DTMs that run forever is not Turing-recognizable

The language A, that is all DTMS that run forever on input. Would this not just be the HALT problem? Therefore no reduction or proof is necessary, other then stating that? ANSWER FOUND: I think i ...
9
votes
5answers
3k views

Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
1
vote
1answer
29 views

Simplest Turing-complete ruleset for Markov algorithm

Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?
-4
votes
1answer
73 views

What is a Universal Turing machine? [closed]

What is a Universal Turing machine and can it really operate like any possible computable algorithm that is represented as a specific Turing machine? I read previously a UTM might work if any turing ...
2
votes
0answers
20 views

Computational models - proving language is decidable [duplicate]

I tried to prove that the following language is recursive/decidable/in R: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_\text{TM,epsilon}\cap \Sigma^k $$ where $H_\text{TM,epsilon}=\{\langle ...
7
votes
3answers
113 views

Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup

I tried to prove that the following language is recursive: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k $$ where ...
1
vote
1answer
31 views

Disprove that a function exists that counts the turing machines that halt on $\epsilon$

Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k $ Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$. I am not sure where I ...
4
votes
1answer
228 views

Official Name for the “First” Programming Language Developed by Turing?

As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions ...
14
votes
5answers
2k views

Why can functional languages be defined as Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
11
votes
5answers
327 views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
6
votes
2answers
71 views

How can a cyclic tag system halt with an output?

For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a ...
2
votes
2answers
80 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
1
vote
1answer
66 views

Checking acceptance of a word vs finding an accepted word

We know that checking whether some word w is accepted by a turing machine TM is undecidable. But what about the problem of finding one accepting word of a TM? Are these two problems related in some ...
1
vote
1answer
45 views

DTM that halts on a minimum one input

I am trying to show that this is Turing Recognizable. The language A, that is a DTM, T, that halts on a minimum of one input. My justification is that of course it is because, you just need to check ...
3
votes
1answer
367 views

The control in the Turing Machine

My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the ...
-1
votes
1answer
31 views

Prove L and {0,1}*-L are recursively enumerable [closed]

Exercise ask : Prove which a binary language L is recursive if and only if both L and {0, 1}* - L are recursively enumerable. Now I try to give a solution: Suppose that L is recursively ...
0
votes
2answers
27 views

Constructible enumerable set

We suppose that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S_1 \cup S_2$ and $S_1 \times S_2$ are also ...
7
votes
3answers
386 views

Standard definition of Turing machine

I have followed two famous book on "Automata and Formal Language Theory": Micheal Sipser's book Jeffrey Ullman and John Hopcroft's book in both books, tuple level definition of Turing machine ...
2
votes
1answer
126 views

Show that the set of all TMs that move only to the right and loop for some input is decidable

I am trying to prove that $\qquad L=\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in } M(w) \text{ the head moves only right and } M(w)\!\uparrow \}$ is decidable. I thought about ...
1
vote
1answer
49 views

Why is my proof wrong for $L = H_{TM} \cap \overline{A_{TM}} $

$A_{TM} = \{<M,w> | $ M is a TM and M accepts w $\}$ $H_{TM} = \{<M,w> | $ M is a TM and M halts on w $\}$ I thought that $L = H_{TM} \cap \overline{A_{TM}} \in R$ But I saw the proof ...
1
vote
2answers
118 views

Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?

Let an infinite language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ? I've understood that the answer is: it ...
1
vote
2answers
46 views

How do you swap consecutive boxes on a Turing Machine tape?

I can't figure out how to swap boxes on a Turing Machine tape. So for example, I have a tape that says a 1 0 1 1 1 0 ^ And I want to move that ...
0
votes
2answers
63 views

How does this Turing machine accept $a^n b^n$?

I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something. They give a pseudocode algorithm for an machine that accepts strings from the ...
0
votes
3answers
52 views

Construct Turing Machine which accepts the language $ww$

I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$. Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second ...
0
votes
0answers
106 views

What is the limit for Turing machines with 2 states and 3 symbols that halt?

I read here that a proof has been offered that a Turing Machine with 2 states and 3 symbols can be universal (in that it is capable of arbitrary finite computations). Even if this proof is accepted, ...
1
vote
1answer
38 views

Can Reduction for Undecidability/Decidability Problems Go Both Ways?

This Problem sparked my question: Does a TM $M$ enter state $q$ on input $w$? I proved it was undecidable in this format using the Halting Problem as a subroutine: ...
3
votes
4answers
479 views

Language of Turing machines that loop on all inputs, recognizable?

Prove that the language Loop Turning Machine = { < M > | M is a TM that loops on all inputs} is recognizable. I feel like $M$ would never halt. To make $M$ recognizable it needs to accept or ...
7
votes
1answer
124 views

Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
-1
votes
1answer
64 views

Determine if the language is $R$

Consider the following language: $$L = \{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \}$$ determine whether or not the language is in $R$. Now, from my ...
0
votes
2answers
89 views

Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable?

This is text of an exercise I am working on: Given a binary encoding scheme for the set of the deterministic Turing machines with alphabet $\{0,1\}$ and a bijective and computable function $f: ...
0
votes
3answers
66 views

Reduction and decidability

Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$ I am trying to understand the following proof that this language $L$ is ...
-1
votes
1answer
50 views

Converting this NFA to Turing Machine

I'm asked to choose a DFA and convert it to NFA and then convert it to Turing machine... I have done the first two parts as follows: DFA: --> NFA: --> Turing machine: ??? I haven't found ...
0
votes
1answer
36 views

How does augmenting linear bounded automata tape alphabets increase memory?

A linear bounded automaton is a Turing machine that is restricted by memory. How would augmenting the tape alphabet of a linear bounded automaton increase its memory? While the memory that the ...
6
votes
4answers
163 views

Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
3
votes
1answer
438 views

Good introduction to Turing's work and complexity theory?

I'm currently an undergrad whose been amazed by what Turing has done for the world. I know there are plenty of other amazing individuals, but Turing's work specifically has always sounded the most ...
2
votes
1answer
71 views

Power of variants of Turing machines

I'm having trouble with this problem as I haven't discovered a good way to determine the power of a Turing machine. I was under the impression that if a Turing machine can perform the same actions ...