This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
Questions tagged [turing-machines]
954 questions
0
votes
0 answers
a question about the Turing machine
Can a Turing machine turn the operation "addition" into "multiplication"?
This is a question proposed by one of my classmates. And my teacher told me "no" without any explanation. So does anybody have any idea about it?
Joey Le Roi
- 31
- 1
0
votes
1 answer
Is this language in $RE$?
I have the following language:
$$ L=\{ \langle M, n \rangle \mid \forall x\in \Sigma^*\ s.t\ |x|=n, M\ doesn't\ reject\ x\} $$
Where $M$ is a TM with finite $\Sigma$ and $\Gamma$.
I think that $L$ is not in $RE$, but I don't know how to prove it. I…
Daniel
- 558
0
votes
0 answers
Explanation of Wikipedia's definition of a function problem
On the Wikipedia article for function problem it currently defines a function problem as follows:
A functional problem $P$ is defined as a relation $R$ over strings of an arbitrary alphabet $\Sigma$: $R\subseteq\Sigma^*\times\Sigma^*$. An algorithm…
Pineapple Fish
- 1,512
0
votes
1 answer
Why can't we try to prove the twin prime conjecture using a Turing machine?
Suppose a Turing machine is fed all the basic axioms and it uses the mathematical inference to prove theorems then using these theorems it proves further theorems and so on. At every iteration it checks whether the "Newly" proven theorem is the twin…
0
votes
0 answers
Halting problem thought experiment
I'm not a mathematician, I barely passed GCSE Maths so the post below is written as I thought it.
Imagine Turing Machine h
h takes an input program, and determines if it halts or not
now imagine a second turning machine h+
h+ takes an input program,…
0
votes
0 answers
What is the "/" notation in this Turing Machine State Transition table?
Looking at this page: https://plato.stanford.edu/entries/turing-machine/#SomeSimpExam
In Table 4 there is a / used in two places: when in state q1 and you read a 0, for example. What does that symbol mean?
nicomp
- 159
0
votes
1 answer
Turing machine representing words having as many $0$ as $1$
Give the diagram of transitions of a Turing machine to a ribbon which
accepts the language on the alphabet $\{0, 1\}$ of the words which contain
as many $0$ as of $1$. (Note well that the $0$ and the $1$ can appear in any
order.)
This problem is…
Robert
- 19
0
votes
1 answer
Is the language $L=\{|M \text{ has 24 states}\}$ recursive?
I know that I cannot use the rice theorem because there are two turing machines that calculate the same function but have different ammount of states. What techniqu can I use to prove that this language is not recursive.
New2Math
- 1,265
0
votes
1 answer
What is the complement of the acceptance problem of a Turing machine?
I know that the acceptance problem of a Turing machine is the problem to decide if for any turing machine $M$, given a string $w$ the Turing machine accepts $w$ or not. If the not acceptance of a string is present on the definition of the acceptance…
Matheus
- 167
0
votes
1 answer
Can we guarantee that the computation on the Turing machine in our case will never stop?
Assume that we have a Turing machine which on an empty input, with $n > 100$ states worked $n^{ n^n}$ steps. Can we guarantee that in this case the computation will never stop?
fenry
- 35
0
votes
1 answer
Writing multiple symbols on a Turing Machine
Just a quick question: is it possible to write multiple symbols in succession onto a tape of a Turing Machine at once?
For example, I'm trying to make a Turing machine that will accept the language of all decimal integers that are a multiple of 3.…
Joy
- 73
0
votes
1 answer
Problem understanding Turing Halting problem
As I understand it in simple language the proof of this goes
Take a program (called oracle below) that will stop if the program it is examining never halts and never halts if the program it is examining halts.
Using this oracle program to examine…
nerak99
- 183
0
votes
1 answer
Decidablility Turing machine
Is it decidable whether a Turing machine takes more than 481 steps for some input?
This was asked in one of the exams. I found some solutions but are not clear to me.
user55531
- 309
0
votes
1 answer
Does this turing machine exist?
I must test whether or not this Turing Machine exists $M(n)=0$ If $n$ is the Gödel number of a Turing Machine that stops with the empty tape $M(n)=1$ in other case.
user636413
0
votes
1 answer
Prove or disprove: Superlanguages of Turing-recognizable languages are themselves Turing-recognizable.
Consider the following claim:
Prove or disprove: If $L_a$ is Turing-recognizable and $L_b$ contains (or equal
to) La, then $L_b$ is recognizable.
I'd love to get a hint or a direction
Thanks in advance
DanielY
- 979