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

learn more… | top users | synonyms

-3
votes
1answer
30 views

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

A = {(M) : M is a DTM that rejects}, B = {(M) : M is a DTM that accept } The languages A and B are disjoint, and are both Turing-recognizable. Prove that there does not exist a decidable language C ⊆ ...
0
votes
1answer
35 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: ...
-3
votes
0answers
17 views

Turing Machine Theortical computer science [on hold]

****Define a bidirectional TM to be a TM whose tapes are infinite in both directions. For every f : {0, 1} -> {0, 1} and time constructible T : N -> N, if f is computable in time T(n) by a ...
1
vote
1answer
23 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
63 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? So the UTM is like a CPU of a computer so any ...
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
106 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
27 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
218 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 ...
13
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
298 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 ...
5
votes
1answer
38 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
76 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
65 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 ...
-3
votes
0answers
13 views

Theoretical Computer Science - halting issue? [duplicate]

Is the following set A recursive ?? M_i is a Turing machine by Gödel number i. A = {i |M_i with input x is halting exactly after 14 steps}.
1
vote
1answer
44 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
364 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
30 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
382 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
56 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
117 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
44 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
50 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, ...
1
vote
1answer
36 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
441 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
119 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
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
45 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
26 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
157 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
428 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
49 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
52 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
29 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
37 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
43 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
45 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
70 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
84 views

simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?
1
vote
1answer
24 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?