turing-machines Questions
2
Solved
I need help designing a turing machine that will compute the following f(x,y) = x*y mod 4. how to approach this problem in binary base where $x$ and $y$ have two bits?
Cryptogenic asked 7/11, 2013 at 12:57
7
Solved
Background
The Von-Neumann architecture describes the stored-program computer where instructions and data are stored in memory and the machine works by changing its internal state, i.e an instruct...
Ulund asked 6/5, 2010 at 14:55
2
Solved
For example, the language of Turing machines that do not accept their own encoding cannot be accepted by any Turing machine.
Killiecrankie asked 26/6, 2012 at 23:37
3
Solved
I am listening the edX lesson, and the professor stresses that every machine able to perform those six basic primitives can be called Turing Complete. But what are the six basic primitives?
Consistory asked 26/1, 2015 at 10:41
3
w^R is the reverse of w and w is {0, 1}* . So the TM needs to decide a word followed by the reverse of this word followed by the word.
I don't want the answer, I just want a lead to start and to ge...
Passably asked 3/10, 2011 at 3:6
14
Solved
What does the expression "Turing Complete" mean?
Can you give a simple explanation, without going into too many theoretical details?
Margarita asked 10/8, 2008 at 18:41
3
Solved
I was wondering what the difference between recursive and recursively enumerable languages is in terms of halting and Turing Machines. I know that recursively enumerable languages are a subset of r...
Eleonoreleonora asked 1/11, 2015 at 20:48
3
Solved
Good Day everyone!
I am trying to solve this Exercise for learning purpose. Can someone guide me in solving these 3 questions?
Like I tried the 1st question for addition of 2 binary numbers sepa...
Extempore asked 26/11, 2019 at 7:33
1
Datalog is not Turing complete.
But what is its computational class?
Is it equivalent to Finite state machine or Pushdown machine (i.e. context free) ... or is it something in between?
Lapp asked 16/1, 2020 at 11:10
11
Solved
What is a Turing machine and why do people keep mentioning it? My IBM PC is all I need to do my computation! Why does anyone care about these machines?
Featly asked 25/10, 2008 at 6:25
3
Solved
I am really struggling with understanding the difference between these two. From my textbook, it essentially describes the difference by saying
a language is co-turing recognizable if it is com...
Lange asked 5/4, 2012 at 16:15
5
Solved
When I am studying about Turing machines and PDAs, I was thinking that the first computing device was the Turing machine.
Hence, I thought that there existed a practical machine called the Turing ...
Biotite asked 9/9, 2011 at 19:25
1
Solved
Let T = {<M> | M is a TM that accepts $w^R$ whenever it accepts w}. Show that T is undecidable
Let T = {<M> | M is a TM that accepts wr whenever it accepts w}.
Show that T is undecidable.
I have two answers to this question - San Diego:
5.9
Let T = { <M> | M is a TM that accep...
Allopath asked 29/4, 2018 at 3:7
1
Solved
I'd like to know how can I calculate function A mod B, where A > B and A, B are unary numbers, with a deterministic turing machine with a single tape.
Thanks
Toadstool asked 25/9, 2017 at 15:55
3
Solved
This is the definition of decidable from Wikipedia
In computability theory, an undecidable problem consists of a family
of instances for which a particular yes/no answer is required, such
that...
Gnat asked 26/2, 2012 at 14:30
1
Solved
Does anyone know of any papers, texts, or other documents that discuss using a hypergraph to implement or represent a nondeterministic Turing machine? Are they in fact equivalent?
I'm pretty sure ...
Yale asked 31/3, 2012 at 7:33
2
I'm trying to wrap my head around lambda calculus, and how it relates to language, compiler and binary code. What it actually means that lambda calculus is equivalent to turing machine, and where i...
Sadowski asked 7/5, 2017 at 9:51
24
Solved
In class, we learned about the halting problem, Turing machines, reductions, etc. A lot of classmates are saying these are all abstract and useless concepts, and there's no real point in knowing th...
Elnaelnar asked 24/10, 2008 at 22:0
2
As far as I know, a Turing machine can be made to execute loops or iterations of instructions encoded on a Tape. This can be done by identifying Line separators and making the Turing machine go bac...
Braden asked 10/4, 2015 at 16:48
1
Solved
So I tried searching for the precise definition of language, but all articles assume that the definition is obvious to everyone. Apparently, to me it isn't.
What is the definition of a Turing machi...
Stretcherbearer asked 20/11, 2015 at 18:17
1
Solved
The Wikipedia Prolog article includes this Turing Machine simulator:
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
perform(qf, Ls, Ls, Rs, Rs)...
Howitzer asked 2/4, 2015 at 0:47
1
Solved
Having the diagram of a DFA, how can I convert it to a Turing Machine? Do I have to find the language that the DFA accepts and then create the Turing Machine? Or is there a direct way?
Thank you.
...
Aimless asked 11/12, 2013 at 0:57
2
Solved
How do you argue for the fact that lambda calculus is Turing complete (in the simplest way possible) ?
Horsewhip asked 8/3, 2012 at 14:23
1
I am reading the book Computational Complexity: A Modern Approach and I am having problems understanding oblivious Turing machines.
An oblivious Turing machine (TM) is such a TM that the movement ...
Printmaker asked 13/2, 2013 at 5:38
1
Solved
I do not the understand the concept of Non Deterministic Turing Machine. I guess I understand the term Non deterministic algorithm : (nondeterministic algorithm is an algorithm that can exhib...
Crinkle asked 23/11, 2012 at 6:19
1 Next >
© 2022 - 2024 — McMap. All rights reserved.