The class to represent a Turing machine. More...

#include <machine/turingMachine.h>

Inheritance diagram for TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >:

[legend]

Collaboration diagram for TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >:

[legend]

Public Types
typedef StorageType::SymbolType	SymbolType
	The type of the symbols on the tape.

typedef TransitionType::HasHalfTape	HasHalfTape
	Whether the tape is a Tape or a HalfTape. More...

Public Member Functions
	TuringMachine ()=default
	The default constructor.

	TuringMachine (const TuringMachine &)=default
	The default copy constructor.

	TuringMachine (TuringMachine &&)=default
	The default move constructor.

TuringMachine &	operator= (const TuringMachine &)=default
	The default copy assignment operator. More...

TuringMachine &	operator= (TuringMachine &&)=default
	The default move assignment operator. More...

virtual	~TuringMachine () override=default
	The default virtual destructor.

virtual bool	isHaltingState (const StateType &state) const noexcept=0
	Test if a given state is a halting one. More...

virtual bool	isHaltingConfiguration (const StateType &state, const StorageType &storage) const noexcept override final
	Test if a given configuration is a halting one. More...

Detailed Description

template<typename TransitionType_, bool deterministic, AcceptingStyle acceptingStyle, template< typename... > class TransitionContainer_ = std::vector, template< typename... > class InitialStateContainer_ = std::vector>
class TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >

The class to represent a Turing machine.

A Turing machine is a machine whose storage is a tape-like: it can be a tape or a half-tape. Moreover, terminal configuration of Turing machines depends only on their current state, not the content of the tape.

This class does not hold any data member. All typedef types in Machine::Machine are still accessible.

Template Parameters

TransitionType_	the type of the transitions of the machine. It must be a derived class of Transition::TuringMachineTransition.
deterministic	a boolean, whether the machine is expected to be deterministic.
acceptingStyle	whether the machine is alternating, regularly accepting, or not.
TransitionContainer_	the container used to return matching transitions. By default, it is std::vector.
InitialStateContainer_	the container used to return initial states. By default, it is std::vector.

These template parameters have the same usage as in Machine::Machine.

Definition at line 33 of file turingMachine.h.

Member Typedef Documentation

◆ HasHalfTape

template<typename TransitionType_ , bool deterministic, AcceptingStyle acceptingStyle, template< typename... > class TransitionContainer_ = std::vector, template< typename... > class InitialStateContainer_ = std::vector>

TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >::HasHalfTape

Whether the tape is a Tape or a HalfTape.

It is std::integral_constant<bool, halfTape> where halfTape is a boolean, which is true if and only if the tape is a half-tape.

Definition at line 59 of file turingMachine.h.

Member Function Documentation

◆ isHaltingConfiguration()

template<typename TransitionType_ , bool deterministic, AcceptingStyle acceptingStyle, template< typename... > class TransitionContainer_ = std::vector, template< typename... > class InitialStateContainer_ = std::vector>

virtual bool TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >::isHaltingConfiguration	(	const StateType &	state,
		const StorageType &	storage
	)		const

inlinefinaloverridevirtualnoexcept

Test if a given configuration is a halting one.

Parameters

[in]	state	a const reference to a StateType. It represents the current state of the machine.
[in]	storage	a const reference to a StorageType. It represents the current memory of the machine.

Returns: whether the current configuration is a terminal configuration.

Parameter state must come from getInitialStates() const, or a sequence of valid transition applications from an initial state.

Termination of Turing machines does not depend on the current storage.

See Machine::isHaltingConfiguration(const StateType& state, const StorageType& storage) const for more details on termination.

Definition at line 123 of file turingMachine.h.

◆ isHaltingState()

template<typename TransitionType_ , bool deterministic, AcceptingStyle acceptingStyle, template< typename... > class TransitionContainer_ = std::vector, template< typename... > class InitialStateContainer_ = std::vector>

virtual bool TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >::isHaltingState ( const StateType & state ) const

pure virtualnoexcept

Test if a given state is a halting one.

Parameters

[in] state a const reference to a StateType. It represents the current state of the machine.

Returns: whether the given state is a terminal state.

Parameter state must come from getInitialStates() const, or a sequence of valid transition applications from an initial state.

Termination of Turing machines does not depend on the current storage.

See Machine::isHaltingConfiguration(const StateType& state, const StorageType& storage) const for more details on termination.

Here is the caller graph for this function:

◆ operator=() [1/2]

template<typename TransitionType_ , bool deterministic, AcceptingStyle acceptingStyle, template< typename... > class TransitionContainer_ = std::vector, template< typename... > class InitialStateContainer_ = std::vector>

TuringMachine& TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >::operator= ( const TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ > & )

default

The default copy assignment operator.

Returns: a reference to *this.

◆ operator=() [2/2]

template<typename TransitionType_ , bool deterministic, AcceptingStyle acceptingStyle, template< typename... > class TransitionContainer_ = std::vector, template< typename... > class InitialStateContainer_ = std::vector>

TuringMachine& TuringSim::Machine::Turing::TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ >::operator= ( TuringMachine< TransitionType_, deterministic, acceptingStyle, TransitionContainer_, InitialStateContainer_ > && )

default

The default move assignment operator.

Returns: a reference to *this.

The documentation for this class was generated from the following file:

include/machine/Turing/turingMachine.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ HasHalfTape

Member Function Documentation

◆ isHaltingConfiguration()

◆ isHaltingState()

◆ operator=() [1/2]

◆ operator=() [2/2]