1. Maszyna Turinga jest to model matematyczny za pomocą którego można zbadać ograniczenia obliczeniowe komputerów. Na potrzeby badań przyjmuje się że maszyny mają nieograniczoną pamięć. Jeżeli jakiś problem może być zrealizowany na maszynie Turinga to można go także rozwiązać na nowoczesnym komputerze. Istnieją problemy, których nie można rozwiązać na żadnej maszynie bądź komputerze np. problem stopu.

2. Działanie maszyny Turinga. Maszyna Turinga składa się z nieskończonej taśmy zawierającej komórki z przetwarzanymi symbolami, ruchomej głowicy zapisująco-odczytującej, układu sterowania głowicą. M = (А, Q, , q_o, q_f , δ ), gdzie A to skończony alfabet, który zapisany jest na taśmie jako dane wejściowe i oznacza symbol pusty, Q są to stany gdzie q_o to stan początkowy, a q_f to stan końcowy układu sterowania, δ to relacja przejścia, czyli w którą stronę ma poruszać się głowica.

3. Problem stopu – nie dla wszystkich algorytmów można zobaczyć czy komputer kończy pracę czy nie. (problem nierozstrzygalny)

4. Deterministyczna maszyna Turinga- ma jedno wejście i jedno wyjście dla stanu (dla każdej pary, stan/symbol ma określone rozwiązanie)

5. Niedeterministyczna maszyna Turinga- ma jedno wejście ale wiele wyjść i nie wiadomo co przyjmie dla danej pary stan/symbol bo ma minimum dwie możliwe czynności do wykonania.

6. Problemy rozstrzygalne – Klasa P – O(n),O(n²), O(n³) (POLINOMID) należą do niej problemy, które mają taką złożoność obliczeniową kiedy ilość operacji jest nie większa niż wielomian. Rozwiązania produkowane są na deterministycznej maszynie Turinga za wielomianowy czas.

Klasa NP O(2n),O(an), O(n!) należą do niej problemy, które mogą być rozwiązywane na niedeterministycznej maszynie Turinga za wielomianowy czas. Często wykorzystane w funkcji silnia bądź w funkcjach wykładniczych.

1. Aproksymacje

- Typu O: f(n)=O(g(n)) oznacza że złożoność czasową problemu można ograniczyć od góry funkcją g(n). Pozwala nam oszacować zachowanie się złożoności obliczeniowej wraz ze wzrostem n do nieskończoności.

- Typu Ω: f(n)=Ω(g(n)) ogranicza funkcję f(n) od dołu i oznacza to że funkcja f(n) jest nie mniejsza niż g(n). Służy do oszacowania działania algorytmu w najlepszym przypadku.

-Typu Θ: Notacja ta ogranicza funkcję f(n) od góry, tak jak notacja O oraz dodatkowo od dołu. wartości funkcji f(n) są niewiększe od wartości funkcji g(n) z dokładnością do stałej c1 wartości funkcji f(n) są niemniejsze od wartości funkcji g(n) z dokładnością do stałej c2

1. Układ kombinacyjny- stan wyjściowy Y zależy wyłącznie od obecnego stanu wejściowego X. Jest to układ cyfrowy bez pamięci Q=0

2. Układ sekwencyjny- stan wyjściowy Y zależy od obecnego stanu wejściowego X oraz od obecnego w danej chwili stanu pamięci Q, które są określane w pewnym czasie. Jest to układ cyfrowy z ograniczoną pamięcią.

3. Automat skończony to matematyczny model układu sekwencyjnego na który składają się: alfabet wejściowy i wyjściowy, alfabet stanów oraz funkcje przejść i wyjść. Automat jest inicjalny jeżeli ma stan początkowy. Jeżeli nie jest inicjalny to każdy ze stanów może być początkowym.

4. Automat Mealy’ego i Moor’a

*Automat Mealy’ego, wartości sygnałów wyjściowych zmieniają się w czasie zmian sygnałów wejściowych, czyli zależą do stanu układu i sygnałów wejściowych

*Automat Moor’a- deterministyczny, wartości sygnałów wyjściowych zależą tylko od stanu w jakim układ się znajduje

*Obydwa te automaty są skończone ponieważ zbiory stanów X Y i Q mają skończoną liczebność. Są deterministyczne, ponieważ funkcje przejść i wyjść są jednoznaczne. Ponadto są zupełne ponieważ funkcje te są określone dla wszystkich możliwych kombinacji swoich argumentów.

1. Układy asynchroniczne- zmiana stanu automatu następuje bezpośrednio pod wpływem zmiany sygnałów wejściowych, opóźnienie wynika z czasu propagacji w elementach, z których jest zbudowany dany układ. Nie ma wejścia sterującego (zegarowego).

2. Układy synchroniczne- zmiana stanu automatu następuje tylko w ściśle określonych chwilach czasu, wyznaczonych przez sygnał sterujący (zegarowy).

3. Tworzenie macierzy przejść i wyjść

x(t) q(t-1)	0	1	2	3
0	3	2	1	3
1	3	2	1	3
2	3	2	1	3
3	3	3	3	3
4	4	4	4	4

Tabela przejść – każdej parze stanów przyporządkujemy nowy stan.

x(t) q(t-1)	0	1	2	3
0	0	0	0	0
1	1	0	0	1
2	1	0	1	1
3	0	0	1	1
4	1	2	3	1

Tabela wyjść- każdej parze stanów przyporządkowujemy sygnał wyjściowy.

x(t) q(t-1)	0	1	2	3
0	3/0	2/0	1/0	3/0
1	3/1	2/0	1/0	3/1
2	3/1	2/0	1/1	3/1
3	3/0	3/0	3/1	3/1
4	4/1	4/2	4/3	4/1

Tabela przejść i wyjść – przejścia licznik, wyjścia mianownik

Graf przejść i wyjść – wierzchołki to stany (0…4). Żeby połączyć wierzchołki i wiedzieć co napisać na krawędziach wykonujemy takie kroki:

x(t) q(t-1)	0
0	3/0

1. Patrzymy na stan z kolumny np. 0

2. Patrzymy na licznik np. 3 Oznacza to, że będziemy mieć połączenie między stanem 0 a 3

3. Opisujemy krawędź stanem z 1 wiersza oraz mianownikiem np. 0/0

Macierz przejść i wyjść- zapisujemy na niej wszystkie wartości z krawędzi (q0 odpowiada wierzchołkowi 0 itd.)

1. Minimalizacja liczby stanów- komputer to maszyna stanów z jednego stanu przechodzi w inny bądź wraca do poprzedniego stanu, przy złej pracy może się zapętlać. Przy projektowaniu np. procesora projektant zakłada i tworzy więcej stanów niż zazwyczaj będzie mu potrzebne. Dlatego tak ważna jest minimalizacja.

2. Bramki logiczne

Najważniejsze bramki logiczne to NAD i NOR ponieważ za ich pomocą można skonstruować wszystkie inne bramki jakimi są (NOT, OR, AND)

Bramki dodatkowe:

Exclusive OR Exclusive NOR

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	0

A	B	A+B
0	0	1
0	1	0
1	0	0
1	1	1