turing-m.cpp

The program simulates a Nondeterministic Multitape Turing Machine. It works as ordinary (Determinist

           << "No Applied Rule"
           << endl;
  }
  cout << endl;


}



// =========
void NondeterministicTuringMachine::show2_situation (
	const string& msg_id_info_i, 
	size_t        configuration_no_i
	) const
{
Tapes_t::const_iterator pos_iter;
const size_t size1 = 5;

  assert (!cur_status_.empty());

  if (configuration_no_i)
  {
    cout << endl;
    if (is_actually_nondeterministic_)
    {
      cout << "\t" << msg_id_info_i << "Branch : " << getstr_processed_branch() << endl;
    }
  }
const string configuration_info (configuration_no_i ? ("Configuration#" + to_string(configuration_no_i)) : "Initial Configuration");
  IF_NOT_EMPTY ((msg_id_info_i + configuration_info), size1, '-');


  cout << "\tState  : " << get_processed_state() << endl;
  //cout << "\t" << string (size2, '-') << endl;

const Tapes_t the_tapes (get_processed_tapes());
  for (pos_iter = the_tapes.begin(); 
       pos_iter != the_tapes.end(); 
       pos_iter++
      )
  {
    cout << "Tape#" << distance (the_tapes.begin(), pos_iter) << " : ";
    show_tape (pos_iter);
  }
  //cout << endl;

}


// =========
void NondeterministicTuringMachine::show_resources_report (const string& msg_i) const
{
const size_t size1 = 5;

  IF_NOT_EMPTY (msg_i, size1, '-');

ostringstream oss, oss2;
const string prefix (3, ' ');
const string li_sign (" * ");
const size_t info_setw = 10;

  oss2 << getstr_id_info (true) << " Resource Report";

  oss << "" 
      << prefix
      << oss2.str()
      << endl

      << prefix
      << string (oss2.str().size(), '-')
      << endl

      << prefix
      << getstr_id_info (true)
      << li_sign
      << "Input size    : "
      << setw (info_setw)
      << std::right
      << input_size_
      << " symbols"
      << endl

      << prefix
      << getstr_id_info (true)
      << li_sign
      << "Output size   : "
      << setw (info_setw)
      << std::right
      << output_size_
      << " symbols"
      << endl

      << prefix
      << getstr_id_info (true)
      << li_sign
      << "TM-Space used : "
      << setw (info_setw)
      << std::right
      << space_used_
      << " cells"
      << endl

      << prefix
      << getstr_id_info (true)
      << li_sign
      << "TM-Time used  : "
      << setw (info_setw)
      << std::right
      << time_used_;
  if (is_actually_nondeterministic_)
  {
    oss << " (smart)";
  }
  oss << " transitions"
      << endl;


  cout << oss.str() << endl << endl << endl;

}


// =========
void NondeterministicTuringMachine::show_statistics (const string& msg_i) const
{
const size_t size1 = 5;

  IF_NOT_EMPTY (msg_i, size1, '-');

uint total = accumulate (transition_statistics_.begin(), transition_statistics_.end(), 0);

const string text_statistics ("Statistics");
const string text_transition ("Transition");
const string text_rules ("Rules");
const string text_times ("Times");
const string text_total ("Total");
const string delim (":");

const size_t max_size1 = MAX_VALUE (text_statistics.size(), text_transition.size());
const size_t the_size2 = 3;
const size_t the_size1 = the_size2 + 1 + max_size1 + 1 + the_size2;
const size_t the_size3 = (the_size1 - 1)/2;
const size_t the_size4 = (the_size1 - 1) - the_size3;
  assert (text_rules.size() < (the_size3 - 1));
  assert (text_times.size() < (the_size4 - 1));

const string l_border ("\t      |");		
const string r_border ("|");		

  cout << l_border << string (the_size1, '=') << r_border << endl;

  cout << l_border 
       << string (the_size2, '-') 
       << " "
       << setw (max_size1)
       << left
       << text_statistics.c_str()
       << " "
       << string (the_size2, '-') 
       << r_border 
       << endl;

  cout << l_border 
       << string (the_size2, '.') 
       << " "
       << setw (max_size1)
       << left
       << text_transition.c_str()
       << " "
       << string (the_size2, '.') 
       << r_border 
       << endl;

  cout << l_border << string (the_size1, '-') << r_border << endl;

  cout << l_border 
       << setw (the_size3 - 1)
       << right
       << text_rules.c_str()
       << " "
       << delim
       << setw (the_size4 - 1)
       << right
       << text_times.c_str()
       << " "
       << r_border 
       << endl;

  cout << l_border << string (the_size1, '-') << r_border << endl;

  for (size_t i = 0; i < transition_statistics_.size(); i++)
  {
    cout << l_border 
         << setw (the_size3 - 1)
         << right
         << i
         << " "
         << delim
         << setw (the_size4 - 1)
         << right
         << transition_statistics_[i]
         << " "
         << r_border 
         << endl;
  }
  cout << l_border << string (the_size1, '-') << r_border << endl;

  cout << l_border 
       << setw (the_size3 - 1)
       << right
       << text_total.c_str()
       << " "
       << delim
       << setw (the_size4 - 1)
       << right
       << total
       << " "
       << r_border 
       << endl;

  cout << l_border << string (the_size1, '=') << r_border << endl;

}


// =========
bool NondeterministicTuringMachine::is_initial_state (const state_t& state_i) const
{
  return (find (initial_states_.begin(), initial_states_.end(), state_i) != initial_states_.end());
}

// =========
bool NondeterministicTuringMachine::is_halting_state (const state_t& state_i) const
{
  return (find (halting_states_.begin(), halting_states_.end(), state_i) != halting_states_.end());
}


// =========
bool NondeterministicTuringMachine::is_internal_state (const state_t& state_i) const
{
  return (find (internal_states_.begin(), internal_states_.end(), state_i) != internal_states_.end());
}

// =========
bool NondeterministicTuringMachine::is_valid_state (const state_t& state_i) const
{
  return (is_initial_state(state_i) || is_halting_state (state_i) || is_internal_state (state_i));
}



// =========
bool NondeterministicTuringMachine::check_states () const
{
bool	ret_bool_value = true;

state_t	phisical_empty_state = string();
vector<state_t>::const_iterator	find_iter;

  assert (!initial_states_.empty());
  assert (!halting_states_.empty());
  assert (!internal_states_.empty());

  // ---------
  find_iter = find (initial_states_.begin(), initial_states_.end(), phisical_empty_state); 
  if (find_iter != initial_states_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Initial state#"
		<< distance (initial_states_.begin(), find_iter)
		<< " is empty : <"
		<< *find_iter
		<< ">"
		);
  }

  find_iter = find (halting_states_.begin(), halting_states_.end(), phisical_empty_state); 
  if (find_iter != halting_states_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Halting state#"
		<< distance (halting_states_.begin(), find_iter)
		<< " is empty : <"
		<< *find_iter
		<< ">"
		);
  }


  find_iter = find (internal_states_.begin(), internal_states_.end(), phisical_empty_state); 
  if (find_iter != internal_states_.end())
  {
    ret_bool_value = false;
    FATAL_MSG	("Internal state#"
		<< distance (internal_states_.begin(), find_iter)
		<< " is empty : <"
		<< *find_iter
		<< ">"
		);
  }

  // ------
vector<state_t> tmp_all_states = get_all_states();
vector<state_t>::iterator	pos_iter;
  for (pos_iter = tmp_all_states.begin(); pos_iter != tmp_all_states.end(); pos_iter++)
  {
    assert (count (pos_iter, tmp_all_states.end(), *pos_iter));
    if (count (pos_iter, tmp_all_states.end(), *pos_iter) > 1)
    {
      ret_bool_value = false;
      FATAL_MSG	("State "
		<< "<"
		<< (*pos_iter)
	 	<< ">"
		<< " occurs more than once"
		);
    }
  }

  // -----------
  return ret_bool_value;
} // check_states


// =========
bool NondeterministicTuringMachine::check_alphabets () const
{
bool	ret_bool_value = true;

Tapes_t::const_iterator	iter;
  for (iter = init_tapes_.begin(); iter != init_tapes_.end(); iter++)
  {
    assert (iter->first == static_cast<size_t> (distance (init_tapes_.begin(), iter)));
    if (!(iter->second.check_alphabet()))	ret_bool_value = false;	
  }

  return ret_bool_value;
}


// =========
bool NondeterministicTuringMachine::check_transition () const
{
bool	ret_bool_value = true;

Transitions_t::const_iterator	pos1_iter;
Tapes_t::const_iterator		pos2_iter;
size_t		i;
state_t		cur_state;
size_t		cur_total_symbols;
symbol_t	cur_symbol;

state_t		next_state;
size_t		next_total_symbols;
symbol_t	next_symbol;
shift_t	shift;

  if (transitions_.empty())
  {
    ret_bool_value = false;
    FATAL_MSG	("No transition function");
  }

  for (pos1_iter = transitions_.begin(); pos1_iter != transitions_.end(); pos1_iter++)
  {
    const string transitions_line_info ("Transition Line#" + to_string (distance (transitions_.begin(), pos1_iter)));
    const string transitions_line_and_tape_no_info (transitions_line_info + ", tape#");

    // --- first ---
    cur_state = pos1_iter->first.get_state();
    cur_total_symbols = pos1_iter->first.get_total_symbols();

    if (!((is_initial_state (cur_state)) || (is_internal_state (cur_state))))
    {
      ret_bool_value = false;
      FATAL_MSG	(transitions_line_info
		<< " : illegal cur-state = <"
		<< cur_state
		<< ">"
		);
    }

    if (cur_total_symbols != init_tapes_.size())
    {
      ret_bool_value = false;
      FATAL_MSG	(transitions_line_info
		<< " : number-of-cur-symbols = "
		<< cur_total_symbols
		<< " is not equal number-of-tapes = "
		<< init_tapes_.size()
		);
    }


    for (i = 0, pos2_iter = init_tapes_.begin(); i < cur_total_symbols; i++, pos2_iter++)
    {
      assert (pos2_iter->first == i);
      cur_symbol = pos1_iter->first.get_symbol(i);

      if (!(pos2_iter->second.is_valid_symbol(cur_symbol)))
      {
        ret_bool_value = false;
        FATAL_MSG	(transitions_line_and_tape_no_info
			<< i
			<< " : illegal cur-symbol = <"
			<< cur_symbol
			<< ">"
			);
      }
    }

    
    // --- second ---
    for (size_t k = 0; k < pos1_iter->second.size(); k++)
    {

      const string transitions_line_second_info (transitions_line_info + "-" + to_string (k + 1));
      const string transitions_line_and_tape_no_second_info (transitions_line_second_info + ", tape#");

      next_state = pos1_iter->second[k].get_state();
      next_total_symbols = pos1_iter->second[k].get_total_symbols();
  
      //if (!((is_halting_state (next_state)) || (is_internal_state (next_state))))
      if (!is_valid_state(next_state))
      {
        ret_bool_value = false;
        FATAL_MSG	(transitions_line_second_info
  		<< " : illegal next-state = <"
  		<< next_state
  		<< ">"
  		);
      }
  
      if (next_total_symbols != init_tapes_.size())
      {
        ret_bool_value = false;
        FATAL_MSG	(transitions_line_second_info
  		<< " : number-of-next-symbols = "
  		<< next_total_symbols
  		<< " is not equal number-of-tapes = "
  		<< init_tapes_.size()
  		);
      }
  
      for (i = 0, pos2_iter = init_tapes_.begin(); i < next_total_symbols; i++, pos2_iter++)
      {
        assert (pos2_iter->first == i);
        next_symbol = pos1_iter->second[k].get_symbol(i);
        shift = pos1_iter->second[k].get_shift(i);
  
        if (!(pos2_iter->second.is_valid_symbol(next_symbol)))
        {
          ret_bool_value = false;
          FATAL_MSG	(transitions_line_and_tape_no_second_info
  			<< i
  			<< " : illegal next-symbol = <"
  			<< next_symbol
  			<< ">"
  			);
        }
  
        if (!(pos2_iter->second.is_valid_shift(shift)))
        {
          ret_bool_value = false;
          FATAL_MSG	(transitions_line_and_tape_no_second_info
  			<< i
  			<< " : illegal shift = <"
  			<< shift
  			<< ">"
  			);
        }
  
      }
  
    } //for (size_t k = 0
 
  } // for (iter = transition.begin(); ...
  return ret_bool_value;
}

	
// =========
void NondeterministicTuringMachine::detect_if_is_actually_nondterministic ()
{
Transitions_t::const_iterator	pos_iter;
  for (pos_iter = transitions_.begin(); pos_iter != transitions_.end(); pos_iter++)
  {
    assert (pos_iter->second.size() > 0);
    if (pos_iter->second.size() > 1)
    {
      is_actually_nondeterministic_ = true;
      break;
    }
  }

}


// =========
bool NondeterministicTuringMachine::get_check_results () const
{
  return check_results_;
}

// =========
string NondeterministicTuringMachine::getstr_id_info (bool detail_flag_i) const
{
ostringstream oss;
  oss << "< ";
  if (detail_flag_i)
  {
    oss << (is_actually_nondeterministic_ ? "N" : "D")
        << "TM #"
        << serial_no_ 
        << ", "
        << "Input #"
        << cur_input_set_no_;
  }
  else
  {
    oss << "Run "
        << serial_no_ 
        << "."
        << cur_input_set_no_;
  }
  oss << " > ";

  return oss.str();
}