Are this statements TRUE or FALSE: Each regular expression defines a language.

Lambda Calculus and Turing Machines are computational models answering the question on what does computable mean.

Predicates output either true or false.

Every multi$-$tape Turing Machine has an equivalent single$-$tape Turing Machine.

Every Context Free Language can be generated by a grammar in the Chomsky Normal Form.

A fixed point of a function is a value that is left unchanged by repeated applications of the function.

A problem if two grammars are equivalent is not decidable.

Both the FSM and FSA acronyms refer to the same concept, the Finite State Machine $($Automaton$).$

A language is regular if and only if it is recognized by some Finite State Machine.

The SAT problem $($propositional satisfiability problem$)$ is an NP$-$complete problem.

The Turing Machine is a computational model that can be considered as a model for all computers.

Pumping lemma for context free languages may be used to prove that certain languages are not context free.

A language is a set of strings.

In Linear Bounded Automata the tape is limited to the size of the input $($which is equivalent to a head of the Turing Machine being limited to move beyond the input part of the TM tape$).$

Rules for transforming one statement into another while preserving truth are referred to as rules of inference or deduction.

Any arbitrary problem can be expressed as a language.

Accordingly to the Church$-$Turing Thesis an algorithmically computable problem is a problem computable by a Turing Machine.

The Turing Machine can be used to decide a language, to recognize a language or to compute a function.

Decidable questions are such questions for which one can write a program that will always terminate.

When a problem's solution can be verified in a polynomial time it can be classified in the NP complexity class.

The big$-$O notation in complexity theory stands for an order of the function characterizing computational resources consumption growth rate on an input size growth.

There exist questions about context$-$free languages that are not decidable.

Regular languages form a subset of context$-$free languages.

A minimal Turing Machine is such that there is no an equivalent TM with a shorter description.

The Recursion theorem can be formulated in the fixed point version.

A logic expression IFF may stand for if and only if$.$

Context Free Languages are generated by Context Free Grammars.

For Deterministic Finite State Machines no randomness means perfect repeatability.

In graph theory vertices are sometimes also referred to as nodes.

The Turing Machine is not necessarily deterministic.

Although most problems are in NP there are problems in PSPACE for which there is no known NP algorithm.

For every Nondeterministic Finite State Machine there is an equivalent Deterministic Finite State Machine.

Space complexity is measured in the number of cells on the tape that the Turing Machine will visit during computation.

It is certain that the PSPACE class is not equal to the EXPSPACE class.

Finding of an efficient $($polynomial$)$ solution for any NP$-$complete problem on a Deterministic Turing Machine will immediately prove that NP and P classes are the same.

Enumeration is not enough to describe a language.

A problem is in the NP complexity class if there is a Nondeterministic Turing Machine that will solve it in polynomial time.

NP is the class of languages that have polynomial$-$time verifiers.

For a computable function the Turing Machine will always halt.

It is possible that the NP class is equal to the EXPTIME class.

We do not know yet whether the P class is equal or not to the EXPTIME class.

G$$del$\text{'}$s Incompleteness Theorems concern the limitations of formal axiomatic systems, not directly about decidability.

The set of rational numbers is countably infinite.

Finite State Machine is typically defined by a $5-$tuple.

Not all languages are Turing recognizable

For Turing Machines there may be two final states.

The P class is certainly not equal to the EXPTIME class.

In Nondeterministic Finite State Machines the next state is chosen at random, which is equivalent to all next states being chosen in parallel.

There are languages which are not Turing recognizable

A language is Turing decidable if and only if there exists some enumerator that enumerates it$.$

The linear complexity class is not considered polynomial time.