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

learn more… | top users | synonyms

0
votes
1answer
30 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
votes
0answers
23 views

Which of the following language is accepted ? which are decided

Would someone verify and possibly correct my understanding . L1 = {< M > M is an algorithm that halts on infinite many inputs}. per my understanding if An algorithm M would halt at finite no of ...
1
vote
1answer
38 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
357 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 ...
-2
votes
0answers
11 views

Prove the existence of a language L such that L and {0,1}$^*-L$ ($\bar L$) aren't recursively enumerable [duplicate]

Prove the existence of a language L such that L and {0,1}$^*-L$ ($\bar L$) aren't recursively enumerable I know that the existence of something is out of the set RE U CO-RE. With Cantor's ...
-1
votes
1answer
27 views

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

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
26 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
364 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
52 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
46 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
109 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
40 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
44 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
40 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
103 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, ...
-2
votes
0answers
40 views

Reduce A Turing Machine that halts on some w and prove undecidability

Show that the following language is undecidable using reduction... HaltEmpty Turing Machine = { < M > | M is a Turing Machine and there exists a string $w \in \Sigma^*$ such that M halts on $w$ } ...
1
vote
1answer
34 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
403 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
90 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
63 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
87 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
62 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
43 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
23 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
156 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
421 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
68 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 ...
2
votes
1answer
47 views

What is a standard way to construct a turing machine for any function to compute

I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example: f(x) = 2x + 3 n>= 0 MIN(x,y) leaves the smallest ...
1
vote
1answer
48 views

m-functions in Turing's paper “On Computable Numbers and applications…”

I was reading Alan Turing's paper "On Computable Numbers with an Application to the Entscheidungsproblem". I was reading well until I encountered "4. Abbreviated Tables", page 235-236, where Turing ...
0
votes
0answers
27 views

How many valid and unique Turing machines are there with restricted states and characters

This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of ...
1
vote
1answer
36 views

Infinite Memory

It seems to me that any problem whose solution requires finite memory can be emulated on a Finite State Machine . This would make those problems that can't be solved by a Finite State Machine to ...
0
votes
1answer
38 views

How many Turing machines are there with $c$ characters and $n$ states?

By $c$ character I mean the numbers $0,\dots,c-1$ and the blank symbol $b$, and by $n$ states I mean $n$ non-accepting states, reject and accept. We can assume every $n$-state Turing machine has ...
0
votes
1answer
43 views

Prove Undecidability: TM M enters each of its states on Input W?

Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$? How to prove that the problem is ...
0
votes
2answers
67 views

Identifying and describing the language accepted by a Turing machine [closed]

Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?
0
votes
2answers
81 views

simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?
1
vote
1answer
23 views

Proving a language to be Recursively Enumerable?

I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L ...
8
votes
8answers
2k views

Why does a Turing machine recognise exactly one language?

I am trying to understand the existence of non-recognisable languages. To get this, I need to know why a Turing machine recognises only one language, not multiple. Why is this?
-1
votes
1answer
71 views

Infinite u decidable languages [closed]

I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the ...
1
vote
2answers
134 views

How is the computational power of a human brain comparing to a turing machine?

This seems related to these questions at a glance: What are some problems which are easily solved by human brain but which would take more time computers? What would show a human mind is/is not ...
0
votes
1answer
49 views

Turing Machine construction

How should I go about building a Turing machine for the following language: L = { $ a^ib^j ∈ (a,b)^* | i ≤ j ≤ 2i $ } I know how to construct a Turing machine for { $ a^nb^nc^n | n ∈ N $ } but ...
1
vote
2answers
122 views

Doubts about infinite language decided by a turing machine

Assume you have an infinite language $L$ over alphabet $\Sigma=\{a,b\}$ For example, $L=\{ax \mid x \in \Sigma^*\}$ Can a Turing Machine, $M$ decide this language? (Generalizing, are all the ...
2
votes
1answer
40 views

Is multiprocessing possible on a turing machine?

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
2
votes
1answer
94 views

$P \neq NP$ and determinism

Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine ...
3
votes
3answers
106 views

Splicing squares on a Turing Machine finite tape

Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The ...
1
vote
3answers
109 views

Understanding definition of NP

In my lecture notes, the definition of the class NP is given as: A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that: For every input $x$, ...
1
vote
3answers
159 views

How to replace one symbol with two on Turing machine's tape

I want to implement following algorithm on Turing machine: rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars (wikipedia) ...
1
vote
2answers
72 views

Proving the set of finite languages is countable without using the union of countable sets

The list of finite languages over a finite alphabet is countable. I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I ...
4
votes
1answer
314 views

Why is automated theorem proving impossible?

As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output. Why is it so?
0
votes
1answer
21 views

Transitions needed for dividing two fixed integers

Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively. A transition is an element of $Q \times \Sigma ...
1
vote
1answer
70 views

How exactly does a two stack pushdown automaton work?

I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good. Now I ...