WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

2021-11-18T06:59:20Z

Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

←Starija inačica		Inačica od 06:59, 18. studenoga 2021.
Redak 24:		Redak 24:
	{{commons\|Turing Machine}}		{{commons\|Turing Machine}}
	* [[Taylor L. Booth]] (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York.		* [[Taylor L. Booth]] (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York.
	* {{~~cite book~~		* {{Citiranje knjige
	\|author = [[John Hopcroft]] and [[Jeffrey Ullman]]		\|author = [[John Hopcroft]] and [[Jeffrey Ullman]]
	\| year = 1979		\| year = 1979
Redak 33:		Redak 33:
	* [[Alan Turing]] (1936), "On Computable Numbers, With an Application to the Entscheidungsproblem", ''Proceedings of the London Mathematical Society'', Series 2, Volume 42 (1936). [http://www.abelard.org/turpap2/tp2-ie.asp Eprint].		* [[Alan Turing]] (1936), "On Computable Numbers, With an Application to the Entscheidungsproblem", ''Proceedings of the London Mathematical Society'', Series 2, Volume 42 (1936). [http://www.abelard.org/turpap2/tp2-ie.asp Eprint].
	* [[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice-Hall, Inc., N.J., 1967.		* [[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice-Hall, Inc., N.J., 1967.
	* {{~~cite book~~		* {{Citiranje knjige
	\| author = Siniša Srbljić		\| author = Siniša Srbljić
	\| title = Jezični procesori 1		\| title = Jezični procesori 1

WikiSysop: Bot: Automatski unos stranica

2021-08-20T00:41:09Z

Bot: Automatski unos stranica

Nova stranica

'''Turingovi strojevi''' su iznimno jednostavni apstraktni uređaji za manipulaciju znakovima (simbolima) koji - unatoč jednostavnosti dizajna - mogu biti prilagođeni da simuliraju logiku bilo kojeg računalnog algoritma (uz sadašnje poimanje algoritma). Opisao ih je 1936. [[Alan Turing]]. Turingovi strojevi ne koriste se u praktične svrhe, već u misaonim eksperimentima, gdje najvažniju primjenu nalaze u istraživanju granica mogućnosti izračunavanja računalnim algoritmima. Proučavanje njihovih svojstava pruža dalekosežne uvide u pitanja [[računalna znanost|računalne znanosti]] i [[teorija složenosti|teorije složenosti]].

Turingov stroj koji može simulirati bilo koji drugi Turingov stroj se zove [[Univerzalni Turingov stroj]] ('''UTS''' ili jednostavno '''univerzalni stroj'''). Više matematički orijentiranu definiciju sa sličnom "univerzalnom" prirodom je uveo [[Alonzo Church]], čiji se rad na [[lambda račun]]u isprepleo sa Turingovim u formalnoj teoriji [[izračunljivost]]i poznatoj kao [[Church-Turingova teza]]. Teza povezuje strogu formalnu definiciju Turingovog stroja i intuitivne ideje izračunljivosti, te na taj način pruža preciznu definiciju [[algoritam|algoritma]] ili 'mehaničkog postupka'.

== Formalna definicija jednotračnog Turingovog stroja ==

Sažeti formalni opis Turingovog stroja:
:"Turingov stroj je [[konačni automat]] povezan sa vanjskim medijem za pohranu ili memoriranje" (Minsky (1967) p. 117)

:"Turingov stroj je esencijalno konačni sekvencijalni stroj koji ima mogućnost komuniciranja s vanjskim spremištem informacija" (Booth (1967), p. 354)

[[Konačni automat]] je predstavljen tablicom stanja i svojim registrom stanja. "Vanjski medij za pohranu" jest traka. Ulaz stroja je pročitani znak sa trake. Izlaz stroja jest znak koji se piše na traku ili naredba za brisanje znaka te naredba za pomicanje trake ulijevo ili udesno.

Hopcroft i Ullman (1979, p. 148) formalno definiraju (jednotračni) Turingov stroj kao uređenu sedmorku <math>M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> gdje
* <math>Q</math> je konačan skup ''stanja''
* <math>\Gamma</math> je konačan skup ''znakova trake'' ([[abeceda (računarstvo)|abeceda]] trake)
* <math>b \in \Gamma</math> je istaknuti znak kojim se označava prazna ćelija (jedini znak kojem je dozvoljeno da bude ispisan na traci beskonačno mnogo puta u svakom koraku izračuna)
* <math>\Sigma</math>, podskup skupa <math>\Gamma</math> ne uključujući b je skup ''ulaznih znakova'' (ili ''ulazna abeceda'')
* <math>\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}</math> je parcijalna funkcija (nije definirana na cijeloj domeni) zvana ''funkcija prijelaza'', gdje je L pomak ulijevo, R pomak udesno.
* <math>q_0 \in Q</math> je ''početno'' ili ''inicijalno'' stanje
* <math>F \subseteq Q</math> je skup ''prihvatljivih'' ili ''finalnih'' stanja

== Izvori ==
{{commons|Turing Machine}}
* [[Taylor L. Booth]] (1967), ''Sequential Machines and Automata Theory'', John Wiley and Sons, Inc., New York.
* {{cite book
|author = [[John Hopcroft]] and [[Jeffrey Ullman]]
| year = 1979
| title = Introduction to Automata Theory, Languages and Computation
| publisher = Addison-Wesley, Reading Mass
| edition = 1st edition
| id = {{ISBN|0-201-02988-X}}.}}
* [[Alan Turing]] (1936), "On Computable Numbers, With an Application to the Entscheidungsproblem", ''Proceedings of the London Mathematical Society'', Series 2, Volume 42 (1936). [http://www.abelard.org/turpap2/tp2-ie.asp Eprint].
* [[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice-Hall, Inc., N.J., 1967.
* {{cite book
| author = Siniša Srbljić
| title = Jezični procesori 1
| publisher = Element
| year = 2003
| id = {{ISBN|953-197-129-3}}}}

{{Formalni jezici i gramatike}}

[[Kategorija:Računski modeli]]
[[Kategorija:Teoretsko računarstvo]]

Turingov stroj - Povijest promjena

WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

WikiSysop: Bot: Automatski unos stranica