Maszyna Turinga

Definicja intuicyjna:
Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej "głowicy", wykonującej proste operacje na zapisanych na taśmie wartościach.

Turmit – dwuwymiarowy model obliczeń będący połączeniem maszyny Turinga i modelu Langtona. Wykazano, że odpowiadają pod względem możliwości obliczeniowych jednowymiarowej maszynie Turinga.

Hiperkomputer – hipotetyczna maszyna obliczeniowa (komputer) dysponująca większą mocą obliczeniową niż maszyna Turinga, tzn. taka, która potrafi wykonywać algorytmy, których nie jest w stanie wykonać maszyna Turinga. Mówimy, że potrafią one wykonywać hiperobliczenia, w odróżnieniu od "zwykłych" obliczeń, które wykonują maszyny Turinga.

Funkcje obliczalne są podstawowym obiektem badań teorii obliczalności. Zbiór funkcji obliczalnych jest równoważny zbiorowi funkcji obliczalnych w sensie Turinga oraz funkcji częściowo rekurencyjnych. Funkcje obliczalne stanowią analogon intuicyjnego pojęcia algorytmu. Tego pojęcia używa się do dyskusji obliczalności bez odniesienia do określonego modelu obliczalności takiego jak maszyna Turinga lub maszyna von Neumana. Jednak ich definicja musi mieć odniesienie do określonego modelu obliczalności.

W teorii obliczalności o maszynie lub języku programowania mówimy, że jest kompletny w sensie Turinga lub zupełny, jeśli można za jego pomocą rozwiązać identyczną klasę problemów obliczeniowych, jak na uproszczonym modelu programowalnego komputera zwanego maszyną Turinga. W praktyce oznacza to, że jeśli dany język lub maszyna potrafi wykonać lub wyrazić każdy algorytm, określany jest mianem zupełnego, przy czym nie jest wymagane, by algorytm ten realizowany był prosto, wydajnie bądź efektywnie.

Pracowity bóbr (ang. busy beaver) to maszyna Turinga o z góry zadanej liczbie stanów N, która zaczynając od pustej taśmy (same zera), generuje jak najdłuższy ciąg jedynek (lub też w innym sformułowaniu: wykonuje jak najwięcej kroków), po czym zatrzymuje się (maszyna, która nie zatrzymuje się jest dyskwalifikowana).

Definicja intuicyjna:
Tensor – uogólnienie pojęcia wektora; wielkość, której własności pozostają identyczne niezależnie od wybranego układu współrzędnych.

Model deterministyczny to model matematyczny, który danemu na wejściu zdarzeniu jednoznacznie przypisuje konkretny stan. Opis modelu nie zawiera żadnego elementu losowości. Oznacza to, że ewolucja układu w modelu deterministycznym jest z góry przesądzona i zależy wyłącznie od parametrów początkowych lub ich wartości poprzednich.

Definicja intuicyjna:
Tensor – uogólnienie pojęcia wektora; wielkość, której własności pozostają identyczne niezależnie od wybranego układu współrzędnych.

Mrówka Langtona to prosty automat komórkowy wymyślony przez Chrisa Langtona. Może być traktowany również jako rozszerzona do dwóch wymiarów bardzo prosta maszyna Turinga.

Granica ciągu – wartość, w której dowolnym otoczeniu znajdują się prawie wszystkie (tzn. wszystkie poza skończenie wieloma) wyrazy danego ciągu; precyzyjniej: wartość, dowolnie blisko której leżą wszystkie wyrazy ciągu o dostatecznie dużych wskaźnikach.

Definicja intuicyjna:
Język rekurencyjny to rodzaj języka formalnego, dla którego mając podane reguły jego składni, da się opracować automatyczny sposób sprawdzania, czy dane słowo jest zbudowane zgodnie z tymi regułami (tzn. należy do języka) czy nie.

Maszyna rejestrowa – maszyna (procesor bądź maszyna wirtualna), w której podstawowe operacje prowadzi się na niewielkiej grupie rejestrów, nie zaś na stosie.

Hipoteza Churcha-Turinga (zwana również Tezą Churcha-Turinga) jest hipotezą określającą możliwości komputerów i innych maszyn obliczeniowych. Mówi ona, że każdy problem, dla którego przy nieograniczonej pamięci oraz zasobach istnieje efektywny algorytm jego rozwiązywania, da się rozwiązać na maszynie Turinga. Hipoteza jest niemożliwa do sprawdzenia matematycznie, ponieważ łączy w sobie zarówno ścisłe, jak i nieprecyzyjne sformułowania, których interpretacja może zależeć od konkretnej osoby. Dlatego traktowana jest bardziej jako aksjomat lub swoiste prawo.

Tablica systoliczna to w automatyce układ przetwarzający o regularnej, modularnej strukturze zbudowany z prostych modułów; jednostek przetwarzających; synchronicznie wykonujących elementarne operacje.

Dane binarne (ang. binary data) — dane zapisane w postaci dwójkowej, tzn. reprezentowane jako ciąg zer i jedynek. Dane zapisane binarnie zajmują mniej miejsca niż dane zapisane alfanumerycznie. Możliwe jest też znacznie wydajniejsze przetwarzanie tak zapisanych danych, gdyż nie istnieje konieczność tłumaczenia odczytywanych danych z postaci alfanumerycznej na binarną i odwrotnie. Dane zapisane binarnie nie są czytelne dla człowieka bez stosowania specjalizowanych narzędzi umożliwiających ich zinterpretowanie.

Wiele metod obliczania pierwiastka kwadratowego z dodatniej liczby rzeczywistej S wymaga wartości początkowej. Jeśli ta wartość jest zbyt odległa od aktualnej wartości pierwiastka, obliczenia będą znacznie wydłużone. w związku z tym jest wysoce pożądane aby mieć oszacowanie tej wielkości, które może być nawet bardzo niedokładne ale proste do wyznaczenia. Jeśli S ≥ 1, niech D będzie liczbą cyfr po lewej stronie przecinka dziesiętnego. Jeśli S < 1, niech D będzie ujemną liczbą zer bezpośrednio na prawo od przecinka dziesiętnego. Wtedy oszacowanie jest następujące:

       na podstawie Wikipedii, otwartej encyklopedii : licencje: GFDL, oraz CC-BY-SA 3.0 + autorzy, historia
edycja