Results 1 to 2 of 2

Math Help - Turing Machine Problems

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    8

    Turing Machine Problems

    Hello,
    Can someone help me on these problems please ?

    1. Consider the task of deciding if any given Turing Machine (TM) will from an initial blank tape ever print a non-blank on the initially scanned square. Assuming the Blank Tape Halting Problem (BTHP) Theorem, show that this task is Turing Impossible.

    2. Let us call any square on a tape currently significant if it is currently non-blank, or if it is currently scanned, or if it lies between two squares each currently non-blank or scanned, and consider the task of deciding if any given TM from an initially blank tape will ever have more than 100 currently significant squares on its tape. Show that this task is Turing Possible.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2008
    Posts
    1

    turing machine to compute n-square?

    can someone help me in designing a turing machine to compute n-square
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing Machine Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2011, 11:14 AM
  2. Turing Machine
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 25th 2010, 06:39 AM
  3. Turing machine
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: August 21st 2010, 07:17 AM
  4. Turing machine: help neeed
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: June 3rd 2008, 12:45 AM
  5. Help on a Turing Machine Question
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: March 23rd 2008, 03:41 AM

Search Tags


/mathhelpforum @mathhelpforum