2 items
Tagged:
  • turing machine x

Start over - to expand, or dig in by adding more tags and revising the query.

Sort By: trending ▼ date
0
Graduate
By John Doe on Nov. 3, 2012 | Updated Dec. 28, 2017

Computability of the space complexity of Turing machines

Show that the space complexity of Turing machines is computable. The space complexity is the partial function \(s:\Sigma^* \times \Sigma^* \to \Sigma^*\) defined as …
0
Undergraduate
By Shiva Kintali on June 14, 2012 | Updated Dec. 6, 2017

Left move is decidable

Consider the problem of determining whether a Turing machine on an input \(w\) ever attempts to move its head left at any point during its computation on \(w\). Show that this problem is decidable.
Post Something
x

Select What You'd Like To Post

POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION

Content Types

Social learning platform. © 2016 True Group Inc. All Right Reserved