Cub11k's BIU Notes

Automata 10

5 min read

Closures

Closure of decidable languages

  • Union
  • Intersection
  • Complement
  • Concatenation
  • Kleene closure

Closure of acceptable languages

  • Union
  • Intersection
  • Concatenation
  • Kleene closure

Relation between decidable and acceptable languages

If the language is decidable, it is also acceptable, this is trivial. If, however, both the language and its complement are acceptable, the language itself is decidable! Proof is by running (simulating) both in parallel, for example with a multi-line Turing machine. If the word is accepted by , it is accepted. If it is accepted by then it is rejected.

Church-Turing thesis

SIMPLE programming language

  • Variables
    • Natural numbers
    • Infinite arrays
  • Operations
    • Assignment (both literal and variable)
    • Addition, Subtraction, Multiplication of natural variables
  • Conditions
    • Equality ()
    • Inequality ()
  • Flow
    • All instructions are numbered, execution is sequential
    • goto allows jumping to an arbitrary instruction
    • stop terminates the program with exit code (0 or 1)

Language of a SIMPLE program

SIMPLE defines a set of all possible computer programs

SIMPLE program is equivalent to Turing machine

This equivalence allows us to write pseudo-code in order to define a Turing machine and conclude that physical computers (up to the finiteness of memory) are equivalent to Turing machine!

General grammars

Similarly to context free grammars, general grammars are sets of derivation rules, but in general grammars, it is possible to put arbitrary strings to the left side of the rule!

Example

On the example of we can show that general grammars can “emulate” the execution of a Turing machine.

Acceptability of a language lemma

Chomsky hierarchy

  • Acceptable languages - General grammar - Turing machine
    • Context-aware languages - Context-aware grammar - Linearly bounded automaton
      • Context-free languages - Context-free grammar - Stack automaton
        • Regular languages - Regular - Finite automaton

Chomsky hierarchy doesn’t provide an answer to the question “Is every CFL decidable?”, but this claim is true! Proof is left out

Church-Turing thesis hypothesis

The Turing machine model embodies the abstract concept of an “algorithm”. That is, any algorithm that can be described as a mechanistic process in which:

  • The process is carried out as a series of steps
  • Each step requires a finite amount of “work”
    Can also be described as a Turing machine. In particular, there is no mechanistic/automatic model more powerful than a Turing machine. This hypothesis still stands today, as there is, yet, no computational models more powerful than a Turing machine.

Graph View