turing-m.cpp

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

// ==============================================================
//
//  Copyright (c) 2002-2003 Alex Vinokur.
//
//  ------------------------------------------------------------
//  This file is part of C++ Simulator of a Nondeterministic Turing Machine.
//
//  C++ Simulator of a Nondeterministic Turing Machine is free software; 
//  you can redistribute it and/or modify it
//  under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License,
//  or (at your option) any later version.
//
//  C++ Simulator of a Nondeterministic Turing Machine is distributed in the hope 
//  that it will be useful, but WITHOUT ANY WARRANTY; 
//  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
//  See the GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with C++ Simulator of a Nondeterministic Turing Machine; 
//  if not, write to the Free Software Foundation, Inc., 
//  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//  ------------------------------------------------------------
// 
//  mailto:[e-mail]
//  http://up.to/alexv
//
// ==============================================================


// ##############################################################
//
//  SOFTWARE : Nondeterministic Turing Machine (C++ Simulator)
//  FILE     : turing-m.cpp
//
//  DESCRIPTION :
//         Class NondeterministicTuringMachine (Implementation)
//
// ##############################################################


// ###############
#include "turing-m.h"


#define	SETW_RULE_NUMBER	4
#define	UNBELIEVABLE_NUMBER_OF_TAPES	100


// =========
size_t	NondeterministicTuringMachine::counter_s (0);
size_t	MachineStatus::next_id_to_be_processed_s (0);


// =========
// =========
// Constructor-0
MachineStatus::MachineStatus ()	: the_configuration_no_(0), the_transition_subno_ (0)
{
}
 

// =========
// Destructor
MachineStatus::~MachineStatus ()
{
} 
		      

// =========
// =========
// Constructor-0
NondeterministicTuringMachine::NondeterministicTuringMachine (
	size_t	number_of_tapes_i,
	// ---
	const vector<vector<string> >& descr_i, 
	const vector<state_t>& initial_states_i, 
	const vector<state_t>& halting_states_i, 
	const vector<state_t>& internal_states_i,
	// ---
	const vector<symbol_t>& empty_symbols_alphabet_i, 
	const vector<symbol_t>& internal_alphabet_i,
	const vector<symbol_t>& input_alphabet_i,
	// ---
	const Transitions_t& transitions_i,
	// ---
	const string& msg_i
	)
	:
	is_actually_nondeterministic_ (false),
	descr_ (descr_i),
	initial_states_ (initial_states_i),
	halting_states_ (halting_states_i),
	internal_states_ (internal_states_i),
	transitions_ (transitions_i),
	check_results_ (true),
	cur_input_set_no_ (0),
	transition_statistics_ (transitions_i.size()),
	max_state_size_ (0),
	max_symbol_size_ (0),
	serial_no_ (++counter_s),
	input_size_ (0),
	output_size_ (0),
	space_used_ (0),
	time_used_ (0)

{

  IF_NOT_EMPTY (msg_i, 5, '=');

typedef Tapes_t::value_type value_type;
pair<Tapes_t::iterator, bool> tapes_pair;

  if (number_of_tapes_i == 0)
  {
    check_results_ = false;
    FATAL_MSG	("Illegal number of tapes : "
		<< number_of_tapes_i
		);
    return;
  }

  if (number_of_tapes_i > UNBELIEVABLE_NUMBER_OF_TAPES)
  {
    WARNING_MSG	("Unbelievable number of tapes : "
		<< number_of_tapes_i
		);
  }

  // -----------------------------------
  for (size_t i = 0; i < number_of_tapes_i; i++)
  {
    tapes_pair = init_tapes_.insert (value_type(i, Tape (empty_symbols_alphabet_i, internal_alphabet_i, input_alphabet_i)));
    if (!tapes_pair.second)
    {
      check_results_ = false;
      FATAL_MSG	("The same current position occurs more than once in transition rules");
      break;
    }
    assert (tapes_pair.second);

    if (!tapes_pair.first->second.check_results_)
    {
      check_results_ = false;
      FATAL_MSG	("Tape#" << i << " has problems");
      break;
    }
  }

  // ------------------------------------
  set_max_state_size();
  set_max_symbol_size();


  // ----------------------
  if (check_results_)	check_results_ = check_states ();
  if (check_results_)	check_results_ = check_alphabets ();
  if (check_results_)	check_results_ = check_transition ();
  detect_if_is_actually_nondterministic ();

  // ---------------
  show_env();

} 

// =========
// Destructor
NondeterministicTuringMachine::~NondeterministicTuringMachine ()
{
} 

// =========
void NondeterministicTuringMachine::set_max_state_size()
{
vector<state_t>	tmp_all_states = get_all_states();
  assert (max_state_size_ == 0);
  for (size_t i = 0; i < tmp_all_states.size(); i++)
  {
    max_state_size_ = MAX_VALUE (max_state_size_, tmp_all_states[i].size()); 
  }

}

// =========
void NondeterministicTuringMachine::set_max_symbol_size()
{
Tapes_t::const_iterator pos_iter;
  assert (max_symbol_size_ == 0);
  for (pos_iter = init_tapes_.begin(); pos_iter != init_tapes_.end(); pos_iter++)
  {
    max_symbol_size_ = MAX_VALUE (max_symbol_size_, pos_iter->second.max_symbol_size_);
  }
}

// =========
vector<state_t> NondeterministicTuringMachine::get_all_states () const
{
vector<state_t>	ret_vector;

  copy (initial_states_.begin(), initial_states_.end(), back_inserter(ret_vector));
  copy (halting_states_.begin(), halting_states_.end(), back_inserter(ret_vector));
  copy (internal_states_.begin(), internal_states_.end(), back_inserter(ret_vector));

  return ret_vector;

}


// =========
void NondeterministicTuringMachine::set_input (
		const vector<vector<symbol_t> >& input_words_i, 
		const vector<long>&              init_pos_i
		)
{
  assert (!cur_status_.empty());
  get_cur_state() = initial_states_.front();

Tapes_t::iterator pos_iter;
  for (pos_iter = get_cur_tapes().begin(); pos_iter != get_cur_tapes().end(); pos_iter++)
  {
    pos_iter->second.clear_it();
  }
  get_cur_tapes().clear();

  get_cur_tapes() = init_tapes_;


  for (size_t i = 0; i < get_cur_tapes().size(); i++) 
  {
    get_cur_tapes()[i].clear_it();
  }

  for (size_t i = 0; i < input_words_i.size(); i++) 
  {
    get_cur_tapes()[i].set_input(input_words_i[i], init_pos_i[i]);
  }

  // --------------------------
  assert (input_size_ == 0);
  for (size_t i = 0; i < input_words_i.size(); i++) 
  {
    if (
         (input_words_i[i].size() == 1) 
         && 
         (get_cur_tapes()[i].is_empty_symbol(input_words_i[i].back()))
       ) 
    {
     continue;
    }

    input_size_ += input_words_i[i].size();
  }

}



// =========
ulong NondeterministicTuringMachine::get_output_size ()
{
ulong ret_value = 0;

  for (size_t i = 0; i < get_cur_tapes().size(); i++) 
  {
    ret_value += get_cur_tapes()[i].get_output_word ().size();
  }

  return ret_value;
}



// =========
ulong NondeterministicTuringMachine::get_space_used ()
{
ulong ret_value = 0;

  for (size_t i = 0; i < get_cur_tapes().size(); i++) 
  {
    ret_value += get_cur_tapes()[i].cell_visits_.size();
  }

  return ret_value;
}


// =========
void NondeterministicTuringMachine::clear_it ()
{
  cur_status_.clear();
  MachineStatus::next_id_to_be_processed_s = 0;
  cur_status_.push_back (MachineStatus());
  assert (!cur_status_.empty());

  cur_input_set_no_++;

  input_size_   = 0;
  output_size_  = 0;
  space_used_   = 0;
  time_used_    = 0;

  for (size_t i = 0; i < transition_statistics_.size(); i++)
  {
    transition_statistics_[i] = 0;
  } 

}


// =========
bool	NondeterministicTuringMachine::check_input_words (
		vector<vector<symbol_t> >& input_words_io,
		vector<long>& init_pos_o
		) const
{
Tapes_t::const_iterator	pos_iter;

  if (input_words_io.empty())
  {
    FATAL_MSG	("No input words");
    return false;
  }

  init_pos_o.clear();
  init_pos_o.resize(input_words_io.size(), HEAD_START_POSITION_DEFAULT);
  assert (init_pos_o.size() == input_words_io.size());

  if (input_words_io.size() != init_tapes_.size())
  {
    FATAL_MSG	("Number of input words ("
		<< input_words_io.size()
		<< ") is NOT equal number of tapes ("
		<< init_tapes_.size()
		<< ")"
		);
    return false;  
  }

size_t i;
  for (i = 0, pos_iter = init_tapes_.begin(); i < input_words_io.size(); i++, pos_iter++)
  {
    assert (pos_iter->first == i);
    if (input_words_io[i].empty())
    {
      FATAL_MSG	("No input word for tape#"
		<< i
		);
      return false;
    }

    vector<symbol_t>::iterator find_iter;
    // ---------------------------------
    const vector<symbol_t> original_input_word (input_words_io[i]);
    find_iter = find (input_words_io[i].begin(), input_words_io[i].end(), HEAD_START_POSITION_POINTER_REDERVED_SYMBOL); 
    if (find_iter != input_words_io[i].end())
    {
      init_pos_o [i] = long (distance (input_words_io[i].begin(), find_iter));
      input_words_io[i].erase(find_iter);
    }

    find_iter = find (input_words_io[i].begin(), input_words_io[i].end(), HEAD_START_POSITION_POINTER_REDERVED_SYMBOL); 
    if (find_iter != input_words_io[i].end())
    {
      ostringstream oss;
      copy (original_input_word.begin(), original_input_word.end(), ostream_iterator<symbol_t> (oss, " "));
      FATAL_MSG	("Tape#"
		<< i
		<< ", input word <"
		<< oss.str()
		<< ">" 
		<< " contains more than one reserved symbol "
		<< "\""
		<< HEAD_START_POSITION_POINTER_REDERVED_SYMBOL
		<< "\""
		<< "; Note! That symbol is used to point at initial position of the machine head"
		);

      return false;
    }


    // ---------------------------------

    for (size_t j = 0; j < input_words_io[i].size(); j++)
    {
      assert (!(input_words_io[i][j] == HEAD_START_POSITION_POINTER_REDERVED_SYMBOL));
      const bool is_input_symbol = pos_iter->second.is_input_symbol (input_words_io[i][j]);
      const bool is_empty_symbol = pos_iter->second.is_empty_symbol (input_words_io[i][j]);
      // old --- if (!((j == 0) && (input_words_io[i].size() == 1) && (pos_iter->second.is_empty_symbol (input_words_io[i][j]))))

      if (!(is_input_symbol || is_empty_symbol))
      {
        FATAL_MSG	("Tape#"
			<< i
			<< ", symbol#"
			<< j
			<< " : "
			<< "\""
			<< input_words_io[i][j]
			<< "\""
			<< " is NOT an input symbol"
			);
        return false;
      }
    } // for (size_t j = 0; ...
  } // for (size_t i = 0; ...

  return true;
}


// =========
void NondeterministicTuringMachine::show_input (
	const vector<vector<symbol_t> >& input_words_i,
	const vector<long>&              init_pos_i,
	bool fool_flag_i
	) const
{
  cout << endl;
  cout << "\t"
       << string (5, '#')
       << " ";
  if (fool_flag_i)
  {
    cout << ""
         << getstr_id_info ();
  }

  cout << "Input word(s) & head start position(s) on tape(s)"
       << " " 
       << string (5, '#')
       << endl;

  assert (input_words_i.size() == init_pos_i.size());

const size_t number_of_tapes = input_words_i.size();
  for (size_t i = 0; i < number_of_tapes; i++)
  {
    cout << "Tape#" << i << " : Word = ";
    for (size_t j = 0; j < input_words_i[i].size(); j++)
    {
      cout << setw (max_symbol_size_) << to_string (input_words_i[i][j]).c_str() << " ";
    }
    cout << ";  Head pos = " << init_pos_i [i];
    //copy (input_words_i[i].begin(), input_words_i[i].end(), ostream_iterator<symbol_t> (cout, " "));
    cout << endl;


  }

  cout << endl;

}




// =========
size_t& NondeterministicTuringMachine::get_cur_configuration()
{
  assert (!cur_status_.empty());
  return cur_status_.back().the_configuration_no_;
}



// =========
size_t NondeterministicTuringMachine::get_processed_configuration() const
{
  assert (!cur_status_.empty());

size_t id;
const bool rc = get_next_id_to_be_processed (id);
  assert (rc);
  assert (id < cur_status_.size());

  return cur_status_[id].the_configuration_no_;
}



// =========
Tapes_t& NondeterministicTuringMachine::get_cur_tapes()
{
  assert (!cur_status_.empty());
  return cur_status_.back().the_tapes_;
}


// =========
Tapes_t NondeterministicTuringMachine::get_processed_tapes() const
{
  assert (!cur_status_.empty());

size_t id;
const bool rc = get_next_id_to_be_processed (id);
  assert (rc);
  assert (id < cur_status_.size());

  return cur_status_[id].the_tapes_;
}


// =========
state_t& NondeterministicTuringMachine::get_cur_state()
{
  assert (!cur_status_.empty());
  return cur_status_.back().the_state_;
}



// =========
state_t NondeterministicTuringMachine::get_processed_state() const
{
  assert (!cur_status_.empty());

size_t id;
const bool rc = get_next_id_to_be_processed (id);
  assert (rc);
  assert (id < cur_status_.size());

  return cur_status_[id].the_state_;
}



// =========
Transitions_t::const_iterator& NondeterministicTuringMachine::get_cur_transition()
{
  assert (!cur_status_.empty());
  return cur_status_.back().the_transition_;
}